兄弟你幾時要交?不如我幫你問下教我2D Game Production個Lecturer點攪lol
佢好勁(應該)

呢個assignment有多少難度。佢有要求Big O唔可以太大定係解到題就得?

TOP

The n-puzzle is a classical problem for modelling algorithms involving heuristics. Commonly used heuristics for this problem include counting the number of misplaced tiles and finding the sum of the Manhattan distances between each block and its position in the goal configuration. Note that both are admissible, i.e., they never overestimate the number of moves left, which ensures optimality for certain search algorithms such as A*.

研究下點用A*去解

TOP

The n-puzzle is a classical problem for modelling algorithms involving heuristics. Commonly used heu ...
Jackass_TMxCK 發表於 2013-11-25 18:59


PM

TOP

本帖最後由 Jimmy0911 於 2013-11-25 21:38 編輯

回復 20# Jackass_TMxCK


oh,sor

TOP

本帖最後由 Jimmy0911 於 2013-11-25 21:38 編輯

多左--------del

TOP

本帖最後由 KoolFreeze 於 2013-11-26 01:05 編輯
開個array
做CHECKING
IF right pattern -> true
DONE

唔洗太複雜
Jimmy0911 發表於 2013-11-24 21:20


How do you check all the configurations of various moves?
Do you know that there are an exponential number of states?
How can you make sure your program run fast enough?

Chess without AI is merely hard-coding.
This problem is more challenging.

TOP

本帖最後由 KoolFreeze 於 2013-11-26 01:43 編輯

Here is the pseudocode of the basic algorithm

IDAStar(State s, int limit) {
    mark state s as visited
    if s is ending state {
        print the path by tracing the predecessor of s
    } else {
       for all neighbour state s' {
           if s' is not visited && limit >= cost of s' + h(s') {
               mark s' as visited
               record s as the predecessor of s'
               IDAStar(s', limit)
           }
       }
   }
}

where h(s') is an admissible heuristic function, for example, sum of manhattan distances of each tiles.

TOP

本帖最後由 神秘二代 於 2013-11-26 01:24 編輯
Here is the pseudocode of the basic algorithm

IDAStar(State s, int limit) {
    mark state s as vis ...
KoolFreeze 發表於 2013-11-26 01:16


IDAStar(s', limit - (cost of s' + h(s')))
why limit - (cost of s' + h(s'))
also, this algorithm not consider more than 1 slot and duplicate number
but as you said, just basic algorithm

TOP

回復 28# 神秘二代

My mistake... No need to update the limit.
Just keep calling IDAStar with an increasing limit until a solution can be found.

TOP

also, this algorithm not consider more than 1 slot and duplicate number
神秘二代 發表於 2013-11-26 01:22


It just depends on how you enumerate neighbour states.

TOP