Backtracking Problem

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Backtracking Problem

    Hallo Leute, ich hoffe ihr könnt mir weiterhelfen.

    Ich will einen Algo in Ruby schreiben, der mir die beste Zugfolge für ein Spiel ausgibt.

    Das Prob ist dabei, dass die wichtigen Variablen, wenn sie in einem Rekursionspfad geändert werden, dass in ALLEn Rekursionspfaden passiert.....?

    der soll sich im Prinzip durchschachteln und stelle für stelle probieren ob die entsprechende Zahl funktioniert und dann wenn keine Zahl mehr gewählt werden kann, die Summe ausrechnen und gucken ob das besser ist, als die bisherigen Ergebnisse.

    (Das Spiel funzt so: man hat eine Zahlenfolge von 1-N. Man kann pro zug 1 Zahl auswählen. Diese Zahl muss aber min. 1 Teiler haben. Wenn man eine Zahl gewählt hat, wird diese aus der Liste gestrichen, sowie deren Teiler. Kann keine Zahl mehr gewählt werden, ist das Spiel vorbei. Bei einer Folge von [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] wäre also [2, 6, 8, 10] möglich. Aber auch [10, 9, 8]. Je höher die Summe, desto besser^^)

    Quellcode

    1. def x_in_a(a, x)
    2. ap = a.index(x)
    3. if ap == nil
    4. return false
    5. else
    6. return true
    7. end
    8. end
    10. def teiler_check(a, zahl)
    11. teiler = []
    12. pos= a.index(zahl)
    13. if pos == nil
    14. pos = a.length-1
    15. end
    16. ii = 0
    17. for i in 0..pos
    18. if (zahl%a[i])==0
    19. if not a[i]==zahl
    20. teiler[ii]=a[i]
    21. ii += 1
    22. end
    23. end
    24. end
    25. return teiler
    26. end
    28. def move(a, u, t, z, x, teiler)
    29. a.delete(x)
    30. for i in 0..(teiler.length-1)
    31. a.delete(teiler[i])
    32. end
    33. up=u.length
    34. u[up]=x
    35. t = t + teiler
    36. end
    38. def ausgeben(u, t)
    39. score = 0
    40. for i in 0..(u.length-1)
    41. if not u[i]==nil
    42. score = score + u[i]
    43. end
    44. end
    45. if @score<score
    46. @score = score
    47. @way = u
    48. p "********"
    49. print "score: "
    50. p score
    51. print "way: "
    52. p @way
    53. p "********"
    54. end
    55. end
    57. def possible(a)
    58. is = 0
    59. i = 0
    60. state = false
    61. until is == 1 or i>=(a.length) do
    62. teiler = teiler_check(a, a[i])
    63. if teiler.length>0
    64. is = 1
    65. state = true
    66. else
    67. i+=1
    68. end
    69. end
    70. return state
    71. end
    73. def taxman(a, t, u, z, stacklvl)
    74. if possible(a)==true
    75. for i in 1..(a.length)
    76. print "stack: "
    77. p stacklvl
    78. x = i
    79. print "x: "
    80. p x
    81. if x_in_a(a, x)==true
    82. teiler=teiler_check(a, x)
    83. print "teiler: "
    84. p teiler
    85. if teiler.length>0
    86. move(a, u, t, z, x, teiler)
    87. print "u: "
    88. p u
    89. p "*****"
    90. taxman(a, t, u, z, stacklvl+1)
    91. end
    93. end
    94. p "********"
    95. end
    96. end
    97. ausgeben(u, t)
    98. end
    100. def setup(l)
    101. a = []
    102. z = []
    103. u = []
    104. t = []
    105. for i in 0..(l-1)
    106. a[i] = (i+1)
    107. z[i] = (i+1)
    109. end
    110. @score = 10
    111. @way = []
    112. taxman(a, t, u, z, 1)
    113. end
    115. setup(10)
    Alles anzeigen

  • Das Prob ist dabei, dass die wichtigen Variablen, wenn sie in einem Rekursionspfad geändert werden, dass in ALLEn Rekursionspfaden passiert.....?

    Ich schätze mal, dass Ruby Objekte standardmäßig als Referenz übergibt und nicht als Kopie.
    Entweder musst du Kopien übergeben oder jede Funktion muss den ausgeführten Zug vor der Rückkehr wieder rückgängig machen. Letztere Methode ist meistens besser weil weniger Speicher benötigt wird.