Algoritm för att hitta alla vägar av längd L med vikt <= V

Tja,


Jag har kört fast på ett jävla störigt problem som jag tror man borde kunna lösa utan brute force.


Jag behöver traversera en graf för att hitta alla vägar mellan två noder av exakt längd L och där nodernas vikter uppgår till max V.

Grafen har ingen riktning och det är OK att besöka samma nod fler gånger.

Jag tänkte att använda en "adjacency matrix" och helt enkelt upphöja denn matris M till L och därefter ta ut element XiYi för antal vägar mellan Xi och Yi. Problemet är att jag samtidigt måste ta ruttens "vikt" i beräkningen. Där har jag kört fast.


Är det någon som har ett förslag på hur man skulle kunna utöka "adjacency"-matrisen så att man får med vikten. Jag har funderat på om man på något sätt skulle kunna göra en liknande matris med bara vikter åså försöka subtrahera bort. Tex på något sätt lista ut hur många rutter det finns mellan två noder av vikt max V.

Någon som kan ge vägledning i hur jag kan ta mig vidare?

Hur hanterar du vikten om du besöker en nod flera gånger?

Måste du ha antalet rutter? Varför räcker det inte med den snabbaste? Låter annars som något du kan använda en form av TSP på.
http://en.wikipedia.org/wiki/Travelling_salesman_problem

Då adderar jag dem. Så ett dubbelbesök på en nod betyder alltså att den vikten läggs till två gånger.

Ytterligare bör tilläggas att avståndet mellan angränsande noder alltid är 1 men alla noder är inte grannar till varandra, det finns dock vägar från alla noder till alla noder. Ala noder antingen har vikt 1 eller 0.


Det är inte TSP. Notera alltså att jag inte är intresserad av mängden av vägar, endast antalet. Att hitta samtliga vägar mellan två noder givet ett avstånd mellan dem går att beräkna effektivt. Att returnera mängden av alla vägar tror jag är NP-svårt eller åtminstone NP-komplett.

Jag måste kunna köra algoritmen för vägar av längde 30-40 så brute force är uteslutet. (En typisk nod har 3-4 grannar).

Vi kan använda det till att lösa knapsack-problemet,
om jag inte gjorde någon tankemiss. Kan ju hända.

Bygg grafen på följande vis

Ö--Ö--Ö ...
X X
O--O--O ....

<---------------->
L

Varje Ö betyder att en sak inte är med knapsacken, O
betyder att den är det. Varje båge från vänster som går
Ö har vikt 0, varje båge till O har vikt motsvarande den
sakens vikt.

En väg kan endast passera genom en av O eller Ö för
varje nivå och ingen nod kan besökas flera gånger.

Notera att NP-kompletta problem har en övre gräns som
är exponentiell (exemplet ovan har 2^sqrt(n) vägar
där n är antalet noder). Detta betyder inte att det inte
finns en algoritm bättre än bruteforce. Ett trivialt exempel
vore att mötas i mitten. Typ bygga en tabell och matcha
vägar från startnod av längd L/2 med vägar från slutnod
av längd L/2.

Edit: Såg att du ville ha antalet vägar. Gör om det till
beslutsproblem och skapa ett orakel för vägar > 0.

Men om vi har en bestämd storlek på grafen (sådär 45 noder), och maxvikten är 2. Då borde man ändå kunna hitta nått snabbt och smidigt va?

Med största säkerhet.

Som jag sa, kör du möt i mitten kommer du få en komplexitet
som maximalt är \sqrt{2^45}. Typ.

Lite spontant:

En sådan algoritm kan ju se ut något i stil med du kör bredden
först på ett djup L/2. Lägg in alla vägar och deras vikter i en
lista Q_1.

Sedan gör du samma från andra noden. Lägg i en lista Q_2.
Sortera Q_1 och Q_2. Du kan direkt ta bort alla värden på
vikten som är högre än 2.

Börja sedan att i = 0: läs första värdet i Q_1. Sätt en pekare j på
sista värdet i Q_2. Om deras summa är mindre än L, då
har du j-i=j st vägar. Öka sedan pekaren i Q_1. Om ovan fortfarande
gäller har du j-i=j-1 vägar till. Om inte minskar du j tills det gäller.

Du gör alltså max |Q_1|+|Q_2| operationer.

Det ger dig en algoritm som är ungefär 2*2^L/2, där i ditt fall L max
kan vara 45.



Hittade de här också [1][2]. Lite extramaterial.


[1] http://cstheory.stackexchange.com/questions/20246/counting-the-number-of-simple-paths-in-undirected-graph
[2] http://stackoverflow.com/questions/18351953/computing-numbers-of-simple-path-in-directed-graph-containing-cycles

Edit: nu antog jag att n log n ≈ n för små n

Tja,

Tack för alla råd. Jag fick nog å gjorde en riktig ful-lösning:

Eftersom jag bara letade efter vägar med vikt max 2 så byggde jag om grafen genom att göra 3 varianter av varje nod. 0N, 1N, 2N beroende på hur mycket vikt som ansamlats vid besök. Så noder med vikt 0 hade kanter mot element av samma ansamlade vikt-status. Medans de noder i lager xN som hade vikt 1 hade kanter mot noder i (x+1)N.

Adjacency-matrisen för detta problem blev 45x45. Jag höjde denna matris till vägarnas längd. Sen summerade jag endast den del av matrisen vars vägar började i delmängden N0.

Inte direkt skalbart, men tror det funkar.