- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我使用 Prolog (Swipl) 实现了 15 拼图游戏。我已经使用曼哈顿启发式实现了 A* 搜索,但现在我需要添加汉明启发式。
你知道如何实现吗?
:- op(400,yfx,'@').
resolver(Estado,MovimientosSolucion) :- evaluar(Estado,0,F),
buscarSolucion([Estado@0@F@[]],S), reverse(S,MovimientosSolucion).
evaluar(Estado,Profundidad,F) :- evaluarCoste(Estado,Coste),
F is Profundidad + Coste.
buscarSolucion([Estado@_@_@MovimientosSolucion|_], MovimientosSolucion) :- solucion(Estado).
buscarSolucion([B|R],S) :- expandir(B,Sucesores),
insertarTodos(Sucesores,R,ListaAbiertos),
buscarSolucion(ListaAbiertos,S).
insertarUno(B,ListaAbiertos,ListaAbiertos) :- nodoRepetido(B,ListaAbiertos), ! .
insertarUno(B,[C|R],[B,C|R]) :- costeMenor(B,C), ! .
insertarUno(B,[B1|R],[B1|S]) :- insertarUno(B,R,S), !.
insertarUno(B,[],[B]).
insertarTodos([F|R],ListaAbiertos1,ListaAbiertos2) :- insertarUno(F,ListaAbiertos1,ListaAbiertos3),
insertarTodos(R,ListaAbiertos3,ListaAbiertos2).
insertarTodos([],ListaAbiertos,ListaAbiertos).
nodoRepetido(Estado@_@_@_, [Estado@_@_@_|_]).
costeMenor( _@_@F1@_ , _@_@F2@_ ) :- F1 < F2.
expandir(Estado@Profundidad@_@S,Sucesores) :- findall(Sucesor@Profundidad1@F@[Movimiento|S],
(Profundidad1 is Profundidad+1,
mover(Estado,Sucesor,Movimiento),
evaluar(Sucesor,Profundidad1,F)), Sucesores).
solucion(1/2/3/4/5/6/7/8/9/10/11/12/13/14/15/0).
manhattan(A/B/C/D/E/F/G/H/I/J/K/L/M/N/O/P, Coste) :- a(A,CosteA), b(B,CosteB), c(C,CosteC), d(D, CosteD),
e(E,CosteE), f(F,CosteF), g(G,CosteG), h(H,CosteH),
i(I,CosteI), j(J,CosteJ), k(K,CosteK), l(L,CosteL),
m(M,CosteM), n(N,CosteN), o(O,CosteO), p(P,CosteP),
Coste is CosteA + CosteB + CosteC + CosteD + CosteE + CosteF + CosteG + CosteH + CosteI + CosteJ + CosteK + CosteL + CosteM + CosteN + CosteO + CosteP.
evaluarCoste(Tablero,Coste) :- hamming_distance(Tablero,Coste).
mover(TableroInicial,TableroFinal,moverArriba) :- moverArriba(TableroInicial,TableroFinal).
mover(TableroInicial,TableroFinal,moverAbajo) :- moverAbajo(TableroInicial,TableroFinal).
mover(TableroInicial,TableroFinal,moverDerecha) :- moverDerecha(TableroInicial,TableroFinal).
mover(TableroInicial,TableroFinal,moverIzquierda) :- moverIzquierda(TableroInicial,TableroFinal).
moverArriba(A/B/C/D/0/F/G/H/I/J/K/L/M/N/O/P,0/B/C/D/A/F/G/H/I/J/K/L/M/N/O/P).
moverArriba(A/B/C/D/E/0/G/H/I/J/K/L/M/N/O/P,A/0/C/D/E/B/G/H/I/J/K/L/M/N/O/P).
moverArriba(A/B/C/D/E/F/0/H/I/J/K/L/M/N/O/P,A/B/0/D/E/F/C/H/I/J/K/L/M/N/O/P).
moverArriba(A/B/C/D/E/F/G/0/I/J/K/L/M/N/O/P,A/B/C/0/E/F/G/D/I/J/K/L/M/N/O/P).
moverArriba(A/B/C/D/E/F/G/H/0/J/K/L/M/N/O/P,A/B/C/D/0/F/G/H/E/J/K/L/M/N/O/P).
moverArriba(A/B/C/D/E/F/G/H/I/0/K/L/M/N/O/P,A/B/C/D/E/0/G/H/I/F/K/L/M/N/O/P).
moverArriba(A/B/C/D/E/F/G/H/I/J/0/L/M/N/O/P,A/B/C/D/E/F/0/H/I/J/G/L/M/N/O/P).
moverArriba(A/B/C/D/E/F/G/H/I/J/K/0/M/N/O/P,A/B/C/D/E/F/G/0/I/J/K/H/M/N/O/P).
moverArriba(A/B/C/D/E/F/G/H/I/J/K/L/0/N/O/P,A/B/C/D/E/F/G/H/0/J/K/L/I/N/O/P).
moverArriba(A/B/C/D/E/F/G/H/I/J/K/L/M/0/O/P,A/B/C/D/E/F/G/H/I/0/K/L/M/J/O/P).
moverArriba(A/B/C/D/E/F/G/H/I/J/K/L/M/N/0/P,A/B/C/D/E/F/G/H/I/J/0/L/M/N/K/P).
moverArriba(A/B/C/D/E/F/G/H/I/J/K/L/M/N/O/0,A/B/C/D/E/F/G/H/I/J/K/0/M/N/O/L).
moverAbajo(0/B/C/D/E/F/G/H/I/J/K/L/M/N/O/P,E/B/C/D/0/F/G/H/I/J/K/L/M/N/O/P).
moverAbajo(A/0/C/D/E/F/G/H/I/J/K/L/M/N/O/P,A/F/C/D/E/0/G/H/I/J/K/L/M/N/O/P).
moverAbajo(A/B/0/D/E/F/G/H/I/J/K/L/M/N/O/P,A/B/G/D/E/F/0/H/I/J/K/L/M/N/O/P).
moverAbajo(A/B/C/0/E/F/G/H/I/J/K/L/M/N/O/P,A/B/C/H/E/F/G/0/I/J/K/L/M/N/O/P).
moverAbajo(A/B/C/D/0/F/G/H/I/J/K/L/M/N/O/P,A/B/C/D/I/F/G/H/0/J/K/L/M/N/O/P).
moverAbajo(A/B/C/D/E/0/G/H/I/J/K/L/M/N/O/P,A/B/C/D/E/J/G/H/I/0/K/L/M/N/O/P).
moverAbajo(A/B/C/D/E/F/0/H/I/J/K/L/M/N/O/P,A/B/C/D/E/F/K/H/I/J/0/L/M/N/O/P).
moverAbajo(A/B/C/D/E/F/G/0/I/J/K/L/M/N/O/P,A/B/C/D/E/F/G/L/I/J/K/0/M/N/O/P).
moverAbajo(A/B/C/D/E/F/G/H/0/J/K/L/M/N/O/P,A/B/C/D/E/F/G/H/M/J/K/L/0/N/O/P).
moverAbajo(A/B/C/D/E/F/G/H/I/0/K/L/M/N/O/P,A/B/C/D/E/F/G/H/I/N/K/L/M/0/O/P).
moverAbajo(A/B/C/D/E/F/G/H/I/J/0/L/M/N/O/P,A/B/C/D/E/F/G/H/I/J/O/L/M/N/0/P).
moverAbajo(A/B/C/D/E/F/G/H/I/J/K/0/M/N/O/P,A/B/C/D/E/F/G/H/I/J/K/P/M/N/O/0).
moverDerecha(0/B/C/D/E/F/G/H/I/J/K/L/M/N/O/P,B/0/C/D/E/F/G/H/I/J/K/L/M/N/O/P).
moverDerecha(A/0/C/D/E/F/G/H/I/J/K/L/M/N/O/P,A/C/0/D/E/F/G/H/I/J/K/L/M/N/O/P).
moverDerecha(A/B/0/D/E/F/G/H/I/J/K/L/M/N/O/P,A/B/D/0/E/F/G/H/I/J/K/L/M/N/O/P).
moverDerecha(A/B/C/D/0/F/G/H/I/J/K/L/M/N/O/P,A/B/C/D/F/0/G/H/I/J/K/L/M/N/O/P).
moverDerecha(A/B/C/D/E/0/G/H/I/J/K/L/M/N/O/P,A/B/C/D/E/G/0/H/I/J/K/L/M/N/O/P).
moverDerecha(A/B/C/D/E/F/0/H/I/J/K/L/M/N/O/P,A/B/C/D/E/F/H/0/I/J/K/L/M/N/O/P).
moverDerecha(A/B/C/D/E/F/G/H/0/J/K/L/M/N/O/P,A/B/C/D/E/F/G/H/J/0/K/L/M/N/O/P).
moverDerecha(A/B/C/D/E/F/G/H/I/0/K/L/M/N/O/P,A/B/C/D/E/F/G/H/I/K/0/L/M/N/O/P).
moverDerecha(A/B/C/D/E/F/G/H/I/J/0/L/M/N/O/P,A/B/C/D/E/F/G/H/I/J/L/0/M/N/O/P).
moverDerecha(A/B/C/D/E/F/G/H/I/J/K/L/0/N/O/P,A/B/C/D/E/F/G/H/I/J/K/L/N/0/O/P).
moverDerecha(A/B/C/D/E/F/G/H/I/J/K/L/M/0/O/P,A/B/C/D/E/F/G/H/I/J/K/L/M/O/0/P).
moverDerecha(A/B/C/D/E/F/G/H/I/J/K/L/M/N/0/P,A/B/C/D/E/F/G/H/I/J/K/L/M/N/P/0).
moverIzquierda(A/0/C/D/E/F/G/H/I/J/K/L/M/N/O/P,0/A/C/D/E/F/G/H/I/J/K/L/M/N/O/P).
moverIzquierda(A/B/0/D/E/F/G/H/I/J/K/L/M/N/O/P,A/0/B/D/E/F/G/H/I/J/K/L/M/N/O/P).
moverIzquierda(A/B/C/0/E/F/G/H/I/J/K/L/M/N/O/P,A/B/0/C/E/F/G/H/I/J/K/L/M/N/O/P).
moverIzquierda(A/B/C/D/E/0/G/H/I/J/K/L/M/N/O/P,A/B/C/D/0/E/G/H/I/J/K/L/M/N/O/P).
moverIzquierda(A/B/C/D/E/F/0/H/I/J/K/L/M/N/O/P,A/B/C/D/E/0/F/H/I/J/K/L/M/N/O/P).
moverIzquierda(A/B/C/D/E/F/G/0/I/J/K/L/M/N/O/P,A/B/C/D/E/F/0/G/I/J/K/L/M/N/O/P).
moverIzquierda(A/B/C/D/E/F/G/H/I/0/K/L/M/N/O/P,A/B/C/D/E/F/G/H/0/I/K/L/M/N/O/P).
moverIzquierda(A/B/C/D/E/F/G/H/I/J/0/L/M/N/O/P,A/B/C/D/E/F/G/H/I/0/J/L/M/N/O/P).
moverIzquierda(A/B/C/D/E/F/G/H/I/J/K/0/M/N/O/P,A/B/C/D/E/F/G/H/I/J/0/K/M/N/O/P).
moverIzquierda(A/B/C/D/E/F/G/H/I/J/K/L/M/0/O/P,A/B/C/D/E/F/G/H/I/J/K/L/0/M/O/P).
moverIzquierda(A/B/C/D/E/F/G/H/I/J/K/L/M/N/0/P,A/B/C/D/E/F/G/H/I/J/K/L/M/0/N/P).
% coste en distancias de cada posicion
a(0,6). a(1,0). a(2,1). a(3,2). a(4,3). a(5,1). a(6,2). a(7,3). a(8,4). a(9,2). a(10,3). a(11,4). a(12,5). a(13,3). a(14,4). a(15,5).
b(0,5). b(1,1). b(2,0). b(3,1). b(4,2). b(5,2). b(6,1). b(7,2). b(8,3). b(9,3). b(10,2). b(11,3). b(12,4). b(13,4). b(14,3). b(15,4).
c(0,4). c(1,2). c(2,1). c(3,0). c(4,1). c(5,3). c(6,2). c(7,1). c(8,2). c(9,4). c(10,3). c(11,2). c(12,3). c(13,5). c(14,4). c(15,3).
d(0,3). d(1,3). d(2,2). d(3,1). d(4,0). d(5,4). d(6,3). d(7,2). d(8,1). d(9,5). d(10,4). d(11,3). d(12,2). d(13,6). d(14,5). d(15,4).
e(0,5). e(1,1). e(2,2). e(3,3). e(4,4). e(5,0). e(6,1). e(7,2). e(8,3). e(9,1). e(10,2). e(11,3). e(12,4). e(13,2). e(14,3). e(15,4).
f(0,4). f(1,2). f(2,1). f(3,2). f(4,3). f(5,1). f(6,0). f(7,1). f(8,2). f(9,2). f(10,1). f(11,2). f(12,3). f(13,3). f(14,2). f(15,3).
g(0,3). g(1,3). g(2,2). g(3,1). g(4,2). g(5,2). g(6,1). g(7,0). g(8,1). g(9,3). g(10,2). g(11,1). g(12,2). g(13,4). g(14,3). g(15,2).
h(0,2). h(1,4). h(2,3). h(3,2). h(4,1). h(5,3). h(6,2). h(7,1). h(8,0). h(9,4). h(10,3). h(11,2). h(12,1). h(13,5). h(14,4). h(15,3).
i(0,4). i(1,2). i(2,3). i(3,4). i(4,5). i(5,1). i(6,2). i(7,3). i(8,4). i(9,0). i(10,1). i(11,2). i(12,3). i(13,1). i(14,2). i(15,3).
j(0,3). j(1,3). j(2,2). j(3,3). j(4,4). j(5,2). j(6,1). j(7,2). j(8,3). j(9,1). j(10,0). j(11,1). j(12,2). j(13,2). j(14,1). j(15,2).
k(0,2). k(1,4). k(2,3). k(3,2). k(4,3). k(5,3). k(6,2). k(7,1). k(8,2). k(9,2). k(10,1). k(11,0). k(12,1). k(13,3). k(14,2). k(15,1).
l(0,1). l(1,5). l(2,4). l(3,3). l(4,2). l(5,4). l(6,3). l(7,2). l(8,1). l(9,3). l(10,2). l(11,1). l(12,0). l(13,4). l(14,3). l(15,2).
m(0,3). m(1,3). m(2,4). m(3,5). m(4,6). m(5,2). m(6,3). m(7,4). m(8,5). m(9,1). m(10,2). m(11,3). m(12,4). m(13,0). m(14,1). m(15,2).
n(0,2). n(1,4). n(2,3). n(3,4). n(4,5). n(5,3). n(6,2). n(7,3). n(8,4). n(9,2). n(10,1). n(11,2). n(12,3). n(13,1). n(14,0). n(15,1).
o(0,1). o(1,5). o(2,4). o(3,3). o(4,4). o(5,4). o(6,3). o(7,2). o(8,3). o(9,3). o(10,2). o(11,1). o(12,2). o(13,2). o(14,1). o(15,0).
p(0,0). p(1,6). p(2,5). p(3,4). p(4,3). p(5,5). p(6,4). p(7,3). p(8,2). p(9,4). p(10,3). p(11,2). p(12,1). p(13,3). p(14,2). p(15,1).
非常感谢
最佳答案
这是 8-puzzle 的解算器,扩展...可能会占用太多内存。它简单地实现了一个贪婪的启发式算法。用 A* 扩展它可能会很有趣......
/* File: fifteen_puzzle.pl
Author: Carlo,,,
Created: Jul 9 2014
Purpose: solve 15-puzzle
*/
:- module(fifteen_puzzle,
[fifteen_puzzle/3
]).
:- use_module(library(nb_set)).
:- use_module(library(plunit)).
%% fifteen_puzzle(+Target, +Start, -Moves) is nondet.
%
% public interface to solver
%
fifteen_puzzle(Target, Start, Moves) :-
empty_nb_set(E),
solve(E, Target, Start, Moves).
%% -- private here --
solve(_, Target, Target, []) :-
!.
solve(S, Target, Current, [Move|Ms]) :-
add_to_seen(S, Current),
setof(Dist-M-Update,
( get_move(Current, P, M),
apply_move(Current, P, M, Update),
distance(Target, Update, Dist)
), Moves),
member(_-Move-U, Moves),
solve(S, Target, U, Ms).
%% get_move(+Board, +P, -Q) is semidet
%
% based only on coords, get next empty cell
%
get_move(Board, P, Q) :-
nth0(P, Board, 0),
coord(P, R, C),
( R < 3, Q is P + 4
; R > 0, Q is P - 4
; C < 3, Q is P + 1
; C > 0, Q is P - 1
).
%% apply_move(+Current, +P, +M, -Update)
%
% swap elements at position P and M
%
apply_move(Current, P, M, Update) :-
assertion(nth0(P, Current, 0)), % constrain to this application usage
( P > M -> (F,S) = (M,P) ; (F,S) = (P,M) ),
nth0(S, Current, Sv, A),
nth0(F, A, Fv, B),
nth0(F, C, Sv, B),
nth0(S, Update, Fv, C).
%% coord(+P, -R, -C)
%
% from linear index to row, col
% size fixed to 4*4
%
coord(P, R, C) :-
R is P // 4,
C is P mod 4.
%% distance(+Current, +Target, -Dist)
%
% compute Manatthan distance between equals values
%
distance(Current, Target, Dist) :-
aggregate_all(sum(D),
( nth0(P, Current, N), coord(P, Rp, Cp),
nth0(Q, Target, N), coord(Q, Rq, Cq),
D is abs(Rp - Rq) + abs(Cp - Cq)
), Dist).
%% add_to_seen(+S, +Current)
%
% fail if already in, else store
%
add_to_seen(S, L) :-
%term_to_atom(L, A),
findall(C, (nth0(I, L, D), C is D*10^I), Cs),
sum_list(Cs, A),
add_nb_set(A, S, true).
:- begin_tests(fifteen_puzzle).
show_square(R) :-
findall(Row, (between(1,4,_), length(Row, 4)), Rows),
append(Rows, R),
nl, maplist(show_row, Rows).
show_row(R) :-
format('~t~d~3+~t~d~3+~t~d~3+~t~d~3+~n', R).
show_solution(P, []) :-
show_square(P).
show_solution(P, [M|Ms]) :-
show_square(P),
nth0(C, P, 0),
apply_move(P, C, M, U),
show_solution(U, Ms).
target( [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0]).
start(0, [1,2,3,4,5,6,7,8,9,10,11,12,0,13,14,15]).
start(1, [1,2,3,4,5,6,7,8,0,10,11,12,9,13,14,15]).
test(0) :- runtest(0).
test(1) :- runtest(1).
runtest(N) :-
target(T),
start(N, S),
fifteen_puzzle(T, S, R),
format('solution of ~d: ~w~n', [N, R]),
show_solution(S, R).
:- end_tests(fifteen_puzzle).
您可以使用 ?- run_tests(fifteen_puzzle).
进行简单测试。
关于search - 如何使用 Manhattan & Hamming Heuristics 解决 Prolog 中的 15-puzzle 范式,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24630245/
我写信是为了解决下面提供的 Codility 问题, 你要 build 一堵石墙。墙应该是直的,长N米,它的厚度应该是恒定的;但是,它应该在不同的地方有不同的高度。墙的高度由 N 个正整数组成的数组
我有一个 N x M 字段,我想创建一个矩阵,其中包含到特定位置的曼哈顿距离。此外,磁场在所有端部环绕(环面)。 我能否在 Numpy 中快速生成它(无需执行缓慢的洪水填充循环)? 例如函数会返回
按照目前的情况,这个问题不适合我们的问答形式。我们希望答案得到事实、引用或专业知识的支持,但这个问题可能会引发辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开,visit the
This is my project佛罗伦萨大学人工智能类(class)。我必须解决一个经典游戏:带有 8 和 15 格的滑动拼图。这是我对通用图搜索算法的实现: public abstract cl
http://coursera.cs.princeton.edu/algs4/assignments/8puzzle.html 根据上述链接计算出的海明和曼哈顿优先级是否正确? For example
本月初 Yahoo!宣布莫吉托框架。他们将在 2012 年将其开源。 我正在寻找有关这个出色框架的更多信息,但没有成功。 我在哪里可以找到它?我需要等到它开源吗? 最佳答案 我认为您将不得不等到它开源
我使用 Prolog (Swipl) 实现了 15 拼图游戏。我已经使用曼哈顿启发式实现了 A* 搜索,但现在我需要添加汉明启发式。 你知道如何实现吗? :- op(400,yfx,'@'). res
我是一名优秀的程序员,十分优秀!