NK05EOPR - Đổi chỗ

[tntxtnt]

có 1 hướng khác là bạn có thể thử tham lam, bằng cách cố định 1 số vị trí loang các vị trí còn lại

mình thử luôn rồi, cố định mấy số đúng vị trí rồi, chỉ thay đổi các số còn lại thôi. Vẫn quá thời gian

void zeroSwappableIndices(int from)
{
    int best = zeroIndex();
    auto swappableIndices = zeroNeighbors[best];
    neighbors.clear();
    std::copy_if(begin(swappableIndices), end(swappableIndices),
        std::back_inserter(neighbors), [best](int i){
            return i == best;
    });
    if (neighbors.empty())
        std::copy_if(begin(swappableIndices), end(swappableIndices),
            std::back_inserter(neighbors), [from,this](int i){
                return i != from && i != this->data[i];
        });
}

cái copy_if đầu tiên là copy đúng cái i nào có giá trị trùng với vị trí của số 0. Nếu có thì return cái này để tiếp theo swap đúng nó luôn. Nếu ko có thì cái copy_if thứ 2 copy những giá trị i mà ko đúng vị trí với trị số của nó (khác from nữa để khỏi bị ngược). Rồi Dijkstra tiếp mấy neighbors này. Vậy mà vân quá thời gian chạy lên tới 950MB mem Mấy cái AC toàn vài MB mem chắc có công thức gì rồi

[AI_Android]

Test khá yếu thì phải, mình thử sinh test chạy hoài ko ra mà vẫn AC
dùng A*

[tntxtnt]

có phải bác tính h() kiểu như số 3 ở vị trí 0 thì cần +1 lần swap, số 9 ở vị trí 11 thì cần 2 lần swap ko?
vd 3 1 2 0 4 5 6 7 8 11 10 9 thì h() là 1+1+2+2 = 6?

[AI_Android]

ừm mình dùng kiểu đấy test thử xem sao ai ngờ đúng =)) đang định ko đúng thì cài hamming =)) may quá

[tntxtnt]

vẫn chạy quá thời gian ~.~

[tntxtnt]

fking finally =)))))) dm nó thật bữa trước làm ra cái hàm h() rồi mà quên cái A* cộng thêm cái g nữa, tính có w = h. Hôm nay ôm cái code cũ ra sửa cái w thành g+h lại thì do code cũ chặt trường hợp tùm lum với xài queue (…???) thay vì priority_queue rồi lộn min_pq nữa. haha 2h sáng cuối cùng cũng ra =)

[sample (<script>alert("hacked")</script>)]

Anh sử dụng std::map không?

[AI_Android]

:3 lâu không code kiểu này phê voãi

[AI_Android]

không chú, anh nghĩ trình chú đọc cái A star là làm được đó

[tntxtnt]

cần map làm gì.

A* y hệt như Dijkstra vậy đó. Dijkstra tính “điểm” hay weight của từng vertex theo công thức w = g, với g là số bước đi từ start tới vertex hiện tại. Vd start là
6 4 1 0 3 5 9 7 2 10 11 8 có g = 0
thì
6 4 1 3 0 5 9 7 2 10 11 8 có g = 1
6 0 1 3 4 5 9 7 2 10 11 8 có g = 2
v.v…

với Dijkstra g có thể được xem là “quá khứ” của vertex hiện tại, và xét vertex tiếp theo dựa trên điểm số “quá khứ”. A* kèm thêm “tương lai” vô công thức tính điểm nữa: w = g + h. Với h là ước lượng số bước đi tối thiểu cần có để đi từ vertex hiện tại tới end. Ở đây “tối thiểu” nghĩa là h ko được ước lượng quá cao mà phải luôn ước lượng <= số bước cần thiết thật sự. Vd 1 0 2 3 4 5 6 7 8 9 10 11 thì chỉ cần 1 lần swap nữa là ra, thì h phải <= 1. Nếu h > 1 thì A* sai.

tìm tối thiểu là khó nhất. Nếu cho h = 0, tức là luôn luôn thỏa điều kiện h <= số bước cần thật sự thì A* trở thành Dijkstra. h càng nhỏ thì A* càng giống với Dijkstra. h càng gần với số bước cần thật sự thì A* càng lẹ. Vì vậy phải tìm 1 cái h sao cho hợp lý.

ở bài này từ 2 điều kiện, vẽ hình cái graph ra ta có:

3 - 4 - 5
|   |   |
0 - 1 - 2
|   |   |
6 - 7 - 8
|   |   |
9 -10 -11 
|   |   |
3 - 4 - 5

tức là vd nếu số 0 ở vị trí 3 thì nó có thể swap với số ở vị trí 0, 4, 9, vd
6 4 1 0 3 5 9 7 2 10 11 8, số 0 có thể swap với số 6, 3, 10.

lưu ý có 1 đặc điểm ở đây là nếu số đã trùng với vị trí của nó rồi thì nó ko cần swap nữa, vd 1 10 2 3 0 5 7 4 8 6 9 11 thì 2, 3, 5, 8, 11 ko cần swap nữa.

với những số ko trùng vị trí của nó, số lần swap tối thiểu là số bước đi từ số đó tới vị trí hiện tại của nó trong cái graph trên. Vd 6 4 1 0 3 5 9 7 2 10 11 8 thì số bước tối thiểu của 6 (đang ở vị trí 0) là số bước đi tối thiểu từ 6 tới 0 trong cái graph trên, hay là 1 lần swap. Tương tự: 4 ở vị trí 1 cần tối thiểu 1 swap, 1-2 cần 1 swap, v.v… tổng cộng ta cần tối thiểu 1 + 1 + 1 + 1 + 1 + 0 + 1 + 0 + 1 + 1 + 1 = 9 lần swap.

tới đây thì gần xong rồi đó. Còn duy nhất trường hợp sai: 1 0 2 3 4 5 6 7 8 9 10 11 thì h tính như trên ra h = 2, sai, overestimate vì chỉ cần 1 swap là đủ. Vậy để cho chắc ăn ta trừ đi số lần swap tại vị trí 0 đi cho chắc. Vd 1 7 2 3 4 5 6 0 8 9 10 11 thì h = 1 + 1 + 2 = 4, phải trừ đi số lần swap của 0-7 là 2 ta còn h=2 là đúng.

làm nháp thì thấy h này gần đúng với số lần swap luôn nên mình chơi w = h luôn, nó chạy ra sai nản quá nên bỏ luôn ko ngờ gà vl ko nhận ra A* cộng thêm cái g nữa là được rồi =)

[sample (<script>alert("hacked")</script>)]

Quá tuyệt!!!