abonnementen ibood.com bol.com Coolblue
  vrijdag 12 januari 2018 @ 22:27:31 #251
302030 Amoeba
Floydiaan.
pi_176464145
quote:
0s.gif Op vrijdag 12 januari 2018 22:20 schreef ronaldoo12 het volgende:

[..]

Hmm.. hoezo zou het mij geen route opleveren? Ik heb n random beginpunt(en om te optimaliseren zou ik dit beginpunt telkens kunnen wijzigen) en vanuit dit beginpunt laat ik sneeuwruimer 1 vertrekken. Doormiddel van het kortste pad algoritme kan ik zien waar hij eindigt nadat hij een uur is bezig geweest. Dit eindpunt is het startpunt van sneeuwruimer 2. Die kiest zijn route op dezelfde wijze zoals sneeuwruimer 1 dat heeft gedaan. Op die manier heeft elk sneeuwruimer zijn eigen route die hij kan doorlopen.
Jazeker kan dat, maar dan moet je nog steeds een eindpunt 'kiezen'. En daarnaast geeft het volgen van zo'n algoritme nog steeds de complicatie dat je dezelfde weg meerdere keren schoon gaat maken.

Nog een tipje, je probleem is equivalent met het 'Route inspection problem' of Chinese Postbodeprobleem. Het goede nieuws is dat het probleem gelukkig niet NP hard is. Op de Engelstalige wiki kun je veel vinden over een mogelijk algoritme.

[ Bericht 2% gewijzigd door Amoeba op 12-01-2018 22:35:57 ]
Fervent tegenstander van het korps lasergamers.
pi_176464660
quote:
0s.gif Op vrijdag 12 januari 2018 22:27 schreef Amoeba het volgende:

[..]

Jazeker kan dat, maar dan moet je nog steeds een eindpunt 'kiezen'. En daarnaast geeft het volgen van zo'n algoritme nog steeds de complicatie dat je dezelfde weg meerdere keren schoon gaat maken.

Nog een tipje, je probleem is equivalent met het 'Route inspection problem' of Chinese Postbodeprobleem. Het goede nieuws is dat het probleem gelukkig niet NP hard is. Op de Engelstalige wiki kun je veel vinden over een mogelijk algoritme.
Ah super, dan zal ik daar naar gaan kijken. Maar een eis die ik dan stel aan het kortste pad algoritme is dat wegen die al geruimd zijn, niet nog is doorlopen mogen worden tenzij niet anders kan.

[ Bericht 4% gewijzigd door ronaldoo12 op 12-01-2018 22:49:59 ]
  vrijdag 12 januari 2018 @ 22:56:43 #253
302030 Amoeba
Floydiaan.
pi_176465069
quote:
0s.gif Op vrijdag 12 januari 2018 22:44 schreef ronaldoo12 het volgende:

[..]

Ah super, dan zal ik daar naar gaan kijken. Maar een eis die ik dan stel aan het kortste pad algoritme is dat wegen die al geruimd zijn, niet nog is doorlopen mogen worden tenzij niet anders kan.
Nogmaals, het is een algoritme om de minimale afstand tussen 2 arbitraire punten in een netwerk te bepalen inclusief route, niet een route die alle punten in het netwerk aandoet.

En als je iets verzint om dat geheugen in te bouwen ga je wel een rekenkundig gedrocht krijgen en blijft van je argument dat je 'cover route' minimaal is weinig over.
Fervent tegenstander van het korps lasergamers.
pi_176536858
Ik heb hier de graaf af van de plattegrond van Delft:

https://imgur.com/a/pihW7

Ik wil dus nu het Chinese postbode algoritme op toepassen maar ik loop een beetje vast met hoe ik het best mijn grafen kan opsplitsen. Ik neem aan dat de sneeuwruimers sneeuw ruimen met een snelheid van 3 km/u. De gemeente Delft wilt nu 3 dingen weten:

1. Het aantal sneeuwruimers dat nodig is om de binnenstad van Delft binnen een uur te ruimen.
2. Het startpunt van elk van deze sneeuwruimers.
3. De route die de sneeuwruimers moeten afleggen.

Ik denk dat al deze drie punten prima te bepalen zijn met het Chinese postbode algoritme. Ik heb zelf bedacht om grafen te maken met een gewicht van maximaal 2800m zodat er 200m speling overblijft voor de wegen die dubbel moeten worden bewandeld. Ik weet alleen niet of dit ideaal is.
  dinsdag 16 januari 2018 @ 11:27:57 #255
132191 -jos-
Money=Power
pi_176538884
quote:
0s.gif Op dinsdag 16 januari 2018 09:50 schreef ronaldoo12 het volgende:
Ik heb hier de graaf af van de plattegrond van Delft:

https://imgur.com/a/pihW7

Ik wil dus nu het Chinese postbode algoritme op toepassen maar ik loop een beetje vast met hoe ik het best mijn grafen kan opsplitsen.
Dat hoef jij niet te doen, dat doet het algoritme voor je.

Ik neem aan dat je kennis hebt van graaftheorie? Een beschrijving (van de simpele versie) van je probleem wordt hier gegeven: https://en.wikipedia.org/(...)#Undirected_solution
De versie die jij probeert op te lossen is het meer algemene k-Chinese postman probleem.

quote:
Ik neem aan dat de sneeuwruimers sneeuw ruimen met een snelheid van 3 km/u. De gemeente Delft wilt nu 3 dingen weten:

1. Het aantal sneeuwruimers dat nodig is om de binnenstad van Delft binnen een uur te ruimen.
2. Het startpunt van elk van deze sneeuwruimers.
3. De route die de sneeuwruimers moeten afleggen.

Ik denk dat al deze drie punten prima te bepalen zijn met het Chinese postbode algoritme. Ik heb zelf bedacht om grafen te maken met een gewicht van maximaal 2800m zodat er 200m speling overblijft voor de wegen die dubbel moeten worden bewandeld. Ik weet alleen niet of dit ideaal is.
Waarom zou je meerdere grafen willen maken?
WEB / [HaxBall #64] Jos is God
Arguing on the Internet is like running in the Special Olympics.
pi_176539093
quote:
0s.gif Op dinsdag 16 januari 2018 11:27 schreef -jos- het volgende:

[..]

Dat hoef jij niet te doen, dat doet het algoritme voor je.

Ik neem aan dat je kennis hebt van graaftheorie? Een beschrijving (van de simpele versie) van je probleem wordt hier gegeven: https://en.wikipedia.org/(...)#Undirected_solution
De versie die jij probeert op te lossen is het meer algemene k-Chinese postman probleem.

[..]

Waarom zou je meerdere grafen willen maken?
Omdat ik voor ieder sneeuwruimer moet bepalen welk route hij moet bewandelen. Elk sneeuwruimer krijgt dus zijn eigen graaf toegewezen. Daarnaast mag de afstand die hij beloopt niet groter zijn dan 3000m omdat dat de afstand is die hij aflegt binnen 1 uur.
  dinsdag 16 januari 2018 @ 11:49:09 #257
132191 -jos-
Money=Power
pi_176539319
quote:
0s.gif Op dinsdag 16 januari 2018 11:37 schreef ronaldoo12 het volgende:

[..]

Omdat ik voor ieder sneeuwruimer moet bepalen welk route hij moet bewandelen. Elk sneeuwruimer krijgt dus zijn eigen graaf toegewezen. Daarnaast mag de afstand die hij beloopt niet groter zijn dan 3000m omdat dat de afstand is die hij aflegt binnen 1 uur.
Je kunt dit probleem niet zomaar opsplitsen in kleinere deelproblemen aangezien de oplossing voor een sneeuwruimer afhankelijk is van de oplossingen voor andere sneeuwruimers.

Voor wat voor soort vak is deze opdracht? Heb je kennis van graaftheorie en van algoritmes?
WEB / [HaxBall #64] Jos is God
Arguing on the Internet is like running in the Special Olympics.
pi_176539492
quote:
0s.gif Op dinsdag 16 januari 2018 11:49 schreef -jos- het volgende:

[..]

Je kunt dit probleem niet zomaar opsplitsen in kleinere deelproblemen aangezien de oplossing voor een sneeuwruimer afhankelijk is van de oplossingen voor andere sneeuwruimers.

Voor wat voor soort vak is deze opdracht? Heb je kennis van graaftheorie en van algoritmes?
Voor een wiskundig praktijkopdracht, een project is 't. Heb wel wat kennis van graaftheorie en algoritmes maar niet gigantisch veel. Ik heb nu bijna de afstand van elk zijde bepaald. Het is voor mij 't belangrijkste dat ik met een oplossing kom, dat dit niet de meest ideale is maakt me niet heel veel uit. Het Chinese postbode algoritme schijnt hier heel goed bij te passen. Ik wil er nu alleen nog voor zorgen dat ik dit algoritme zo goed mogelijk toepas.
abonnementen ibood.com bol.com Coolblue
Forum Opties
Forumhop:
Hop naar:
(afkorting, bv 'KLB')