In the previous Chapter 3 , I have explained that I got a bad surprise trying to avoid initialisation and use sequence nodes numbers to save and retrieve results from duplicated subtrees: When cutting some sequence disappears and what was the initial location for the result doesn't exist anymore and you need to dive when not expected. I tried several solutions and it hasn't work. Hope not completely lost.
I fell back to memory initialization with the pgm <salesman-3DIcache.c> . I got a results that sometimes doesn't fit the reference (12 towns). I need to find the bug.
Generated datas can be verified with the help of the pgm <salesman.v1.c> that is making the computation in a simple way at leaf. In salesman-3DIcache.c I only compute the best distance. It was simpler to verify if it is working.
All new datas (make and several sources) can be found in drive salesman2 and the old in salesman.
This is the pgm salesman.v1.c: a reference used for verifying data out of salesman-3DIcache.
The next source below is the pgm salesman-3DIcache.c: an attempt to cache datas and cut duplicated subtrees. It is bugged!!
This version use permutations of 2 towns. I think that in order to get polynomial result, we need to use permutations of much more towns. I haven't yet really worked on P/NP evaluation of this pgm version: I am still busy trying to debug it. But I am still thinking to the future. How will I compare two permutations? Perhaps by ordering the part of the branch nodes from root to the current node and inserting at each level a new town in the ordered list. Explanation:
I have 10 towns {0,1,....9}. Considering a branch described from root to leaf by (0,3,1,2,4...9) we could do:
- level 0 we get (0)
- level 1 we order (0) + 3 ang get (0,3)
- level 2 we order (0,3) + 2 and get (0,2,3)
Aucun commentaire:
Enregistrer un commentaire