Daan - User contributions [en]

Global Traffic

2013-11-21T16:25:49Z

77.251.89.9:

[[Image:globaltraffic.gif|thumb|right| Deze pic moet geupdate worden!]]

==Inleiding==
De nieuw opgerichte Nederlandse maatschappij Mokum Airways (MAW) Amsterdam als thuisbasis en landingsrechten voor 21 verschillende bestemmingen, allen in Europa. Ze heeft een herkenbaar logo en een luchtvloot, bestaande uit toestellen van het type Boeing 737-400 (zie afbeelding onder). Mokum Airlines heeft een marktonderzoek gedaan voor de luchthavens waarop zij actief is waarbij gekeken is hoeveel mensen er potentieel tussen twee luchthavens vervoerd zouden kunnen worden door Mokum Airways.

==Opdracht==
[[Image:mawboeing.gif|frame|right]]
Het doel van deze opdracht is een 'dienstregeling' op te stellen zodat er zoveel mogelijk passagiers vervoerd worden. Mokum Airways maakt winst door zoveel mogelijk passagiers over zoveel mogelijk afstand te vervoeren. Dus wanneer een vliegtuig 10 passagiers 10 kilometer vervoert heeft, dan bedraagt het totaal aantal passagiers-kilometers 100. Maar passagiers gaan niet extra betalen om ver om te vliegen. Dus als een passagier van Amsterdam naar München vliegt via een omweg, telt de afstand Amsterdam-München, niet de omweg.

1. Maak een correcte dagroute voor één vliegtuig, zodat er zoveel mogelijk passagiers over zoveel kilometers verplaatst worden. De score voor een schema is het aantal passagiers vermenigvuldigd met het aantal kilometers tussen haar start- en eindpunt.

2. Maak een correct dagschema voor ''alle zes'' de vliegtuigen uit de vloot, zodat er zoveel mogelijk passagiers over zoveel kilometers verplaatst worden. De score voor een schema is het aantal passagiers vermenigvuldigd met het aantal kilometers tussen haar start- en eindpunt.

==Advanced==

Mokum airlines zoekt een nieuwe thuishaven om haar passagierskilometers verder te optimaliseren. Is er een betere thuishaven dan Amsterdam te vinden? Geef een gegrond advies.

==Technische Requirements==

Een correcte dagroute voor een vliegtuig voldoet aan de volgende eisen:

* Het begin- en eindpunt zijn gelijk.
* Het vliegtuig komt vanwege personeelswissels tenminste éénmaal in Amsterdam.
* Het vliegtuig landt niet en stijgt niet op tussen 2:00 en 6:00 's nachts
* Een vliegtuig heeft een maximumcapaciteit van 147 personen
* Een vliegtuig kan maximaal 3600 kilometer vliegen op een volle tank, en mag onder geen beding zonder brandstof raken.
* Een vliegtuig heeft tussen twee luchthavens een gemiddelde snelheid van 800 km/u

* Een vliegtuig moet na een landing een uur blijven staan voor unboarding, schoonmaak en boarding alvorens weer op kunnen stijgen.
* Een vliegtuig kan op een luchthaven voltanken, maar moet dan een uur extra blijven staan.

==Resources==

'''Nota Bene''' Je moet aardig kunnen progammeren om deze opdracht te kunnen doen; ondanks het voortreffelijke werk van Ruben Balk is de opgave wat ingewikkelder uitgepakt dan aanvankelijk voorzien. Ze staat op de nominatie om integraal omgebouwd te worden tot simulator.

Er is [http://wiki.phoib.net/resources/GlobalTraffic_Sourcecode.zip java-sourcecode] beschikbaar die je kunt gebruiken, zodat je je kunt richten op het maken van het algoritme. De code bevat bijvoorbeeld al een representatie, methoden om die representatie te veranderen, methoden om een route af te drukken en methoden om het aantal passagiers-kilometers te berekenen. Die code maakt gebruik van een applet, en daarom kan je de code niet aanroepen in de commandline als "java globalTraffic" maar met "appletviewer globalTraffic.html". Je kunt uiteraard ook eclipse of een andere omgeving gebruiken.

Ook kan je, nadat je de java files gecompiled hebt, het globalTraffic.html bestandje direct openen in je browser. In dit geval hoef je dus geen gebruik te maken van appletviewer.

In principe waakt de code niet voor constraint violations. Dus het checkt niet op begin- en eindpunt, duur van een route, bereik en of Amsterdam bezocht wordt. Sterker nog, het is mogelijk routes te maken die bestaan uit: Amsterdam -> Amsterdam -> Amsterdam etc. Er wordt echter WEL een melding gegeven wanneer een vliegtuig naar een plek wil vliegen die verder weg ligt dan zijn bereik (dus ookal heeft het vliegtuig een volle tank). Het blijft enkel een melding, je moet zelf er dus voor zorgen dat er aan de constraints voldaan wordt.

De applet bestaat uit een kaartje waarop de routes getekend worden. Wanneer meerdere vliegtuigen tussen twee steden gevlogen hebben, dan kan je alleen de lijn zien van het vliegtuig dat het laatst getekend is.

Verder zie je een scrollbar waarmee je de tijdlijn in en uit kunt zoomen. Daarnaast een redraw knop die een nieuwe route maakt en ook aan het begin ervoor zorgt dat het kaartje afgebeeld wordt.

De tijdlijn geeft de meeste informatie. Elke rij staat voor een vliegtuig en elk vliegtuig heeft een eigen kleur. Daarnaast zie je de duur in minuten van de route die het vliegtuig vliegt. Vervolgens zie je de beginstad van het vliegtuig en pas vanaf 6 uur begint de daadwerkelijke route. Eerst de grondtijd (in de kleur van de stad). Dan zie je in het grijs de tijd dat het vliegtuig in de lucht is. Elke landing is een balkje in de kleur van de stad. Een witte omlijning geeft de minimale grondtijd aan van het vliegtuig. Als het gekleurde balkje verder gaat dan deze gekleurde omlijning, dan is dit dus de extra grondtijd. Wanneer een vliegtuig tankt zie je geen witte omlijning maar rode omlijning. Als de ruimte het toelaat kun je de totale grondtijd in minuten zien tussen de haakjes achter de naam van de stad.

[[Image:Applet.jpg]]

==Known Issues Source Code==

* In MokumFrame.java staan de volgende regels verwisseld:
29: GlobalTraffic traffic = new GlobalTraffic(schaal, redrawButton);

31: redrawButton = new Button("Redraw!");

* De afstand tussen steden hoort symmetrisch te zijn. Enkel in Landing.java is de int 2d-array AFSTAND dat niet voor Amsterdam-Athene:2163 en Athene-Amsterdam:2161.

==Terug==

Terug naar de [[Heuristieken|Heuristieken hoofdpagina]].

Building Brains

2013-11-21T16:25:11Z

77.251.89.9:

[[Image:Buildingbrains.jpg|thumb|right]]

==Inleiding==

[[Image:swactivity.gif|thumb|right|Een netwerk van hersenactiviteit laat een small-world structuur zien.]]

Dit is een netwerken-opdracht. Small-worlds zijn netwerken met een hoge cluster coefficiënt en een lage karakteristieke padlengte. Oftewel: sterk geclusterde netwerken waarin alles goed verbonden is. Van een willekeurig netwerk kun je de cluster coefficiënt en de padlengte vrij makkelijk berekenen; een stukje code hiervoor is al geschreven in de klasse "Jeronimusgraaf", die je vindt in dit [[http://wiki.phoib.net/resources/buildingbrains.java bestand]] met daarin ook de code voor een applet.

Het internet, het menselijk brein en de Japanse taal zijn small-world netwerken. Zie ook de [http://wiki.phoib.net/resources/tutorial_SWN.pdf korte tutorial]. Het is daarom belangrijk veel te weten te komen over de eigenschappen van deze netwerken, en de uitkomsten van de opdracht zullen later mogelijk gebruikt worden om verder onderzoek te doen.

==Opdracht==

1. Vind de maximale en de minimale cluster coefficiënt van een netwerk van 100 knopen en 300 verbindingen, en zorg ervoor dat geen enkele node een graad lager dan drie heeft. Maak duidelijk hoe de graaf eruit ziet. Let op dat de graaf verbonden blijft.

2. Vind de maximale en de minimale karakteristieke padlengte van een netwerk van 100 knopen en 300 verbindingen, en zorg ervoor dat geen enkele node een graad lager dan drie heeft. Maak duidelijk hoe de graaf eruit ziet. Let op dat de graaf verbonden blijft.

3. Vind de maximale en de minimale cluster coefficiënt van een netwerk van 100 knopen en 300 verbindingen terwijl de padlengte maximaal is. Zorg ervoor dat geen enkele node een graad lager dan drie heeft. Maak duidelijk hoe de graaf eruit ziet. Let op dat de graaf verbonden blijft.

4. Vind de maximale en de minimale cluster coefficiënt van een netwerk van 100 knopen en 300 verbindingen terwijl de padlengte minimaal is. Zorg ervoor dat geen enkele node een graad lager dan drie heeft. Maak duidelijk hoe de graaf eruit ziet. Let op dat de graaf verbonden blijft.

==Advanced==

* Vind de grenzen van de CC/CPL-ruimte voor een netwerk van 200 knopen en 600 verbindingen met node-graden hoger dan drie en plot deze in een 2d-grafiek.

* Vind de grenzen van de CC/CPL-ruimte voor een netwerk van 200 knopen en 600 verbindingen met node-graden lager dan negen en plot deze in een 2d-grafiek.

==Links==

Terug naar de [[Heuristieken|Heuristieken hoofdpagina]].

Couveuse

2013-11-05T19:21:17Z

77.251.89.9:

== Welkom in de couveuse ==

De couveuse is een plaats waar spontaan ontsproten ideeën voor het vak [[AI-course]] langzaam worden uitgebroed.

== Global Traffic ==

Poging tot ombouwen naar simulatie:
https://github.com/Jelleas/MokumAirlinesPython/releases

== Programmeertalen en compilersnelheid==

Deze suggestie is geleverd door Dr. Dion Gijswijt (CWI / Univ. Leiden). Het lijkt erg te raken aan formele talen (programmeertalen), berekenbaarheid een compilervraagstukken, zoals interpretatiesnelheid. De nog premature casus gaat als volgt:

We bekijken woorden opgebouwd uit de drie letters T, A en M. Zo’n woord mag je met behulp van de volgende spelregels veranderen:

1) Je mag een M veranderen in MT.

2) Je mag een T veranderen in TA.

3) Je mag een A veranderen in TAM.

4) Twee gelijke letters die naast elkaar staan mag je wegstrepen.

De casus:

Je hebt twee woorden, namelijk 1:MATTAMAMAT en 2:TATAMATMT.

Welke set regels verandert woord 1 in woord 2?

Welke set regels verandert woord 2 in woord 1?

Maak twee andere random woorden en vind nogmaals twee regelsets.

== Opties voor tegelzetten ==

In de huidige vorm zijn alle sets in alle vakken een fit. Het is mogelijk te kijken naar sets die niet precies een fit zijn.

== Local Traffic ==

De opdracht: maak een dagschema voor de stoplichten van stadsdeel Nieuw-Noord. De kwaliteit van het dagschema is de totale wachttijd van alle auto's opgeteld dus hoe lager de score, hoe beter. Auto's komen op vaste tijden aan en rijden een vaaste route. Dit is niet erg realistisch, maar we willen graag eerst even kijken hoe de opgave uitpakt voordat we de restricties versoepelen, of stochastische complexiteit toevoegen.

* Deterministische toevoer van auto’s in de vorm van tabel 1.
* Verschillende intensiteit: ochtend- en avondspits

[[Image:Heuristieken_autoInput.png]]

'''Wegennet van Nieuw-Noord'''

* Niet elk kruispunt heeft banen voor linksaf, rechtsaf en rechtdoor.
* Op een wegdeel tussen 2 kruispunten kan maar een beperkt aantal auto’s staan (?)

[[Image:Heuristieken_wegennet.png]]

Wenselijk is een simulator die laat zien hoe een rooster presteert, directe score teruggeven is misschien voldoende voor een eerste-versie opgave.

[[Image:Heuristieken_roosterVoorbeeld.png]]

Hard constraints:
* Alle auto’s moeten hun bestemming bereiken
* Stoplichten mogen niet dusdanig ingesteld staan dat ongelukken gebeuren

Nog te bepalen:
* Exacte kruispuntconfiguratie
* Auto-aankomsttijdentabel

== Ziekenhuizen voor Haiti ==
Een jaar na de zware aardbeving die het hele land in puin legde, zijn er nog steeds grote problemen in Haiti. Zo is er nog altijd nauwelijks medische hulp in het hele land. Er is echter hoop: de VN is van plan ziekenhuizen te bouwen waarmee het hele land gecoverd zal worden. De vraag is echter: welk type en waar moeten de ziekenhuizen geplaatst worden?

'''Opdracht'''

Bepaal waar, welk type ziekenhuis moet worden gebouwd, z.d.d. de kosten per geholpen patiënt zo laag mogelijk zijn.

'''Gegevens'''

[[Image:Kaart_haiti.PNG]]

Er zijn drie type ziekenhuizen die gebouwd kunnen worden, namelijk:

{| border="1"
|+ De type ziekenhuizen
! !! Prijs !! Maximaal aantal patiënten per jaar !! Maximale reisafstand *
|-
! Klein
| || ||
|-
! Midden
| || ||
|-
! Groot
| || ||
|}

Verder is ook gegeven een lijst met het inwonersaantal per stad.

'''Restricties A'''
* Je mag alleen bouwen in de steden.
* 50% van de bevolking gaat in een jaar naar een ziekenhuis.
* Elke zieke patiënt moet verzorgt worden.

'''Restricties B'''
* Je mag overal in het land bouwen.
* 50% van de bevolking gaat in een jaar naar een ziekenhuis.
* Elke zieke patiënt moet naar een ziekenhuis kunnen.

'''Advanced'''

In plaats van de deterministische “vraag” naar zorg, kan deze stochastisch worden gegenereerd a.h.v. een verdeling.

'''Nog te bepalen'''

De optimale waardes voor de tabel van de ziekenhuizen, z.d.d. de oplossing niet triviaal is. Verder kan natuurlijk ook het aantal steden nog worden uitgebreid / verminderd.

== Ideeën voor Amstelhaege ==

* De afstand van een huis tot dichtstbijzijnde water als variabele

* Dynamische component: huizen zijn niet altijd even veel waard maar varieren binnen een bepaalde range (waarbij prijzen van maisons het meest schommelen, eengezins meer stabiel).

* Een standbeeld dat vooral veel waard is in de buurt van maisons, maar minder in de goedkopere wijken

* Een verhouding tussen wegen (waardeverbetering, maar milieuvermindering)en natuurgebied (milieuverbetering)

* Stel: Huizen hebben alleen ramen aan voor- en achterkant, en een huis wordt meer waard als er geen 'inkijk' vanuit andere huizen is.

== Ideeën voor nieuwe opgaven ==

* Callcenter en distributie van bellers

* (Som)Sudoku-solver

* het bepalen van de moeilijkheidsgraad van een Calcudoku puzzel (voorbeeld Calcudoku's op http://www.321monkey.nl/calcudoku)

** Gerelateerd is: hoeveel verschillende Calcudoku puzzels zijn er mogelijk, gegeven een grootte, aantal bewerkingen, en maximale "hokgrootte"? (bijv. 4x4, 2 bewerkingen, maximale hokgrootte 2)

* Supply-chain management. Verschillende machines produceren verschillende onderdelen van een auto

* 3D-traject met verschuiving en rotatie. Een bankstel in een Amsterdams trappenhuis.

* NS-uitval. Het valt op dat iedere keer als er een trein ontspoort of een wissel bevriest, de gevolgen niet beperkt blijven tot een kleine verstoring, maar vaak verstrekkende gevolgen hebben voor de dienstregeling. In ander woorden: de stabiliteit is niet heel groot. Hoe komt dat, en hoe kunnen we hier een opgave mee maken?

* Liften zo programmeren dat de gemiddelde wachttijd het kortst is.

* Zendmasten met een bepaald bereik, tegen kosten van het plaatsen.

* (Ziekenhuis) rooster voor het inboeken van personeel.

* Apotheek(voorraad) De levering van verschillende stoffen met verschillende houdbaarheden die samengesteld verschillende medicijnen vormen.

* Directieplanning; leden van bestuur moeten afhankelijk van de vergadering samen of alleen ergens aanwezig zijn.

* In het 8-queens problem moet je acht koninginnen op een schaakbord zetten zonder dat ze elkaar slaan. Hoeveel oplossingen zijn er, en hoeveel daarvan zijn er ''symmetrisch''. Doe dit voor een 9x9, 10x10 of ander formaat schaakbord nogmaals.

* Tot nu toe zijn alle opgaven deterministisch. Kunnen we iets met een simulatie of een stochast?

==Kladblok==

Hier ga ik eventjes wat links neerzetten die interessant zouden kunnen zijn.

Een [http://www.youtube.com/watch?v=M6V-TvwqwnU lecture van een indiase professor] over AI.

Een [https://class.coursera.org/algo-004/lecture/preview verzameling filmpjes over complexiteit] op Coursera van Tim Roughgarden.

Een cursus die ik ook nog wil gaan volgen op Coursera, over [https://www.coursera.org/course/gametheory Game Theory].

En nog eentje, over [https://www.coursera.org/course/gametheory Game Theory].

En deze lijkt me ook helemaal [https://www.coursera.org/course/optimization te gek].

==Terug==

Terug naar de [[Heuristieken|Heuristieken hoofdpagina]].

Building Brains

2013-11-04T11:04:03Z

77.251.89.9:

[[Image:Buildingbrains.jpg|thumb|right]]

==Inleiding==

[[Image:swactivity.gif|thumb|right|Een netwerk van hersenactiviteit laat een small-world structuur zien.]]

Dit is een netwerken-opdracht. Small-worlds zijn netwerken met een hoge cluster coefficiënt en een lage karakteristieke padlengte. Oftewel: sterk geclusterde netwerken waarin alles goed verbonden is. Van een willekeurig netwerk kun je de cluster coefficiënt en de padlengte vrij makkelijk berekenen; een stukje code hiervoor is al geschreven in de klasse "Jeronimusgraaf", die je vindt in dit [[http://wiki.phoib.net/resources/buildingbrains.java bestand]] met daarin ook de code voor een applet.

Het internet, het menselijk brein en de Japanse taal zijn small-world netwerken. Zie ook de [http://wiki.phoib.net/resources/tutorial_SWN.pdf korte tutorial]. Het is daarom belangrijk veel te weten te komen over de eigenschappen van deze netwerken, en de uitkomsten van de opdracht zullen later mogelijk gebruikt worden om verder onderzoek te doen.

==Opdracht==

1. Vind de maximale en de minimale cluster coefficiënt van een netwerk van 100 knopen en 300 verbindingen, en zorg ervoor dat geen enkele node een graad lager dan drie heeft. Maak duidelijk hoe de graaf eruit ziet. Let op dat de graaf verbonden blijft.

2. Vind de maximale en de minimale karakteristieke padlengte van een netwerk van 100 knopen en 300 verbindingen, en zorg ervoor dat geen enkele node een graad lager dan drie heeft. Maak duidelijk hoe de graaf eruit ziet. Let op dat de graaf verbonden blijft.

3. Vind de maximale en de minimale cluster coefficiënt van een netwerk van 100 knopen en 300 verbindingen terwijl de padlengte maximaal is. Zorg ervoor dat geen enkele node een graad lager dan drie heeft. Maak duidelijk hoe de graaf eruit ziet. Let op dat de graaf verbonden blijft.

4. Vind de maximale en de minimale cluster coefficiënt van een netwerk van 100 knopen en 300 verbindingen terwijl de padlengte minimaal is. Zorg ervoor dat geen enkele node een graad lager dan drie heeft. Maak duidelijk hoe de graaf eruit ziet. Let op dat de graaf verbonden blijft.

==Advanced==

* Vind de grenzen van de CC/CPL-ruimte voor een netwerk van 200 knopen en 600 verbindingen met node-graden hoger dan drie en plot deze in een 2d-grafiek.

* Vind de grenzen van de CC/CPL-ruimte voor een netwerk van 200 knopen en 600 verbindingen met node-graden lager dan negen en plot deze in een 2d-grafiek.

==Known Issues Source Code==

* In MokumFrame.java staan de volgende regels verwisseld:
29: GlobalTraffic traffic = new GlobalTraffic(schaal, redrawButton);

31: redrawButton = new Button("Redraw!");

* De afstand tussen steden hoort symmetrisch te zijn. Enkel in Landing.java is de int 2d-array AFSTAND dat niet voor Amsterdam-Athene:2163 en Athene-Amsterdam:2161.

==Links==

Terug naar de [[Heuristieken|Heuristieken hoofdpagina]].