Waarom is de route heen en terug in Google Maps soms verschillend? Ik heb hier een voorbeeld in Amsterdam, van Amsteldijk 105 naar het Haarlemmermeerstation. Heen is de aanbevolen fietsroute 4,4 km, en terug 5,5 km.
Ok, schrijf jij maar een algoritme dat zegt: "ok, geef me de kortste route van A naar B, maar die hele lange omwegen hoef je niet te beschouwen". Ok, zegt de computer "geef me de lange omwegen zodat ik weet welke ik niet hoef te beschouwen". En rekenen maar...king nero schreef: ↑zo 21 aug 2022, 19:00 Ik ben het in principe niet eens met Arjan. Google geeft je de meest efficiënte oplossing. In dit geval zal je enkel moeten zoeken waarom die als meest efficiënt wordt beschouwd, dus op welke parameters er beoordeeld wordt.
Ik ga niet op de letter spelen, "de beste" of "de meest efficiënte" is voor interpretatie vatbaar, maar ze gaan voor zoiets ook geen wegen via Rome overwegen, dus die jaren rekenwerk valt weg.
Ik ben het eens met King Nero. De computer hoeft helemaal niet alle lange omwegen te berekenen. Bijvoorbeeld, zodra je één willekeurige route van 5 km hebt gevonden, kun je je gelijk beperken tot alle kruispunten die binnen een straal van 5 km liggen van je vertrekpunt liggen. Alle wegen die naar een kruispunt verder dan dat leiden kun je dan wegstrepen, en dus hou je nog maar een heel beperkt aantal mogelijke wegen over. De computer zou dat zonder al teveel problemen helemaal door moeten kunnen rekenen.irArjan schreef: ↑wo 24 aug 2022, 11:07Ok, schrijf jij maar een algoritme dat zegt: "ok, geef me de kortste route van A naar B, maar die hele lange omwegen hoef je niet te beschouwen". Ok, zegt de computer "geef me de lange omwegen zodat ik weet welke ik niet hoef te beschouwen". En rekenen maar...king nero schreef: ↑zo 21 aug 2022, 19:00 Ik ben het in principe niet eens met Arjan. Google geeft je de meest efficiënte oplossing. In dit geval zal je enkel moeten zoeken waarom die als meest efficiënt wordt beschouwd, dus op welke parameters er beoordeeld wordt.
Ik ga niet op de letter spelen, "de beste" of "de meest efficiënte" is voor interpretatie vatbaar, maar ze gaan voor zoiets ook geen wegen via Rome overwegen, dus die jaren rekenwerk valt weg.
Wat voor een mens overduidelijk is, is dat voor een computer niet per se. Wat ik probeer te zeggen is dat het algoritme niet feilloos is, het neemt dingen aan zodat het vele opties niet hoeft te beschouwen. Ik weet helaas niet precies hoe die algoritmes werken, maar blijkbaar is het een combinatie van een Greedy algoritme (dat gewoon alleen kijkt naar de kortste volgende node) en iets dat A* algoritme heet, zie hier
AlsirArjan schreef: ↑wo 24 aug 2022, 11:07Ok, schrijf jij maar een algoritme dat zegt: "ok, geef me de kortste route van A naar B, maar die hele lange omwegen hoef je niet te beschouwen". Ok, zegt de computer "geef me de lange omwegen zodat ik weet welke ik niet hoef te beschouwen". En rekenen maar...king nero schreef: ↑zo 21 aug 2022, 19:00 Ik ben het in principe niet eens met Arjan. Google geeft je de meest efficiënte oplossing. In dit geval zal je enkel moeten zoeken waarom die als meest efficiënt wordt beschouwd, dus op welke parameters er beoordeeld wordt.
Ik ga niet op de letter spelen, "de beste" of "de meest efficiënte" is voor interpretatie vatbaar, maar ze gaan voor zoiets ook geen wegen via Rome overwegen, dus die jaren rekenwerk valt weg.
Wat voor een mens overduidelijk is, is dat voor een computer niet per se. Wat ik probeer te zeggen is dat het algoritme niet feilloos is, het neemt dingen aan zodat het vele opties niet hoeft te beschouwen. Ik weet helaas niet precies hoe die algoritmes werken, maar blijkbaar is het een combinatie van een Greedy algoritme (dat gewoon alleen kijkt naar de kortste volgende node) en iets dat A* algoritme heet, zie hier
Klinkt lekker belerend, dank u... Maar dit is natuurlijk niet generiek en daarmee geen oplossing... De gebruikte algoritmes werken anders, maar dat is niet het punt...
Klopt, natuurlijk klopt dit, dat heb ik ook nooit ontkend. Routeren kan op kleine computers juist omdat veel opties worden weggelaten...
Maar dit klopt niet wat je hier zegt.
Wat ik begrijp is dat het A* algoritme wordt gebruikt. Dit is het Dijkstra algoritme + heuristiek, zie hier en hier. Dit algoritme bepaald niet met 100% zekerheid het de kortste oplossing (maar ws voor kleine afstanden in de meeste gevallen wel met 99% zekerheid of whatever...).
Ik weet niet welke algoritmes en heuristieken ze precies gebruiken, maar dat doet er ook niet toe, want ik reageerde alleen maar op jouw uitspraak:irArjan schreef: ↑do 25 aug 2022, 14:24Wat ik begrijp is dat het A* algoritme wordt gebruikt. Dit is het Dijkstra algoritme + heuristiek, zie hier en hier. Dit algoritme bepaald niet met 100% zekerheid het de kortste oplossing (maar ws voor kleine afstanden in de meeste gevallen wel met 99% zekerheid of whatever...).
Ik kan me vanuit mijn kant niet voorstellen dat ze een uitzondering gaan maken in hun manier van berekenen voor kleine afstanden. Voor kleine en grote afstanden wordt gewoon hetzelfde algoritme gebuikt, daar gaan ze geen onderscheid in maken. Dat betekent dat ook voor kleine afstanden geen 100% zekerheid hebt.
en die uitspraak klopt simpelweg niet. Het is prima mogelijk om een algoritme te verzinnen dat allerlei opties weglaat, maar alsnog gegarandeerd de optimale oplossing vindt. Een standaard A* algoritme bijvoorbeeld, doet precies dat (maar dat wil niet zeggen dat dat ook geldt voor de variant die Google gebruikt, want daar weet ik niks vanaf).het verzinnen van een algoritme dat die opties weg laat per definitie ervoor zorgt dat je niet meer met absolute zekerheid kan zeggen dat de gevonden route ook inderdaad de meest optimale is.