1. Text Classification?
Text Classification adalah tugas untuk menentukan kategori yang telahdi tetapkan ke free-text documents.Text Classification bisa menyediakan conceptual view dari document collections yang mempunyai aplikasi penting di dunia nyata.
Text classification juga bisa digunakan untuk menyaring spam.
Contoh : berita – berita baru biasanya di atur dan di tempatkan di kategori subject yang sesuai agar mudah di cari.

Pesan email yang kita terima juga di kategorikan antara non spam dan spam. text classification ini mendeteksi dan menyaring nya.

 

2.Information Retrieval

Information Retrieval merupakan suatu pencarian informasi (biasanya berupa dokumen) yang didasarkan pada suatu query (inputanuser) yang diharapkan dapat memenuhi keinginan user dari kumpulan dokumen yang ada. Contoh yang paling sering di gunakan dalam information retrieval adalah mesin pencari(search engine) yang ada pada www(world wide web)

Sedangkan, definisi query dalam Information Retrieval menurut referensi merupakan sebuah formula yang digunakan untuk mencari informasi yang dibutuhkan oleh user, dalam bentuk yang paling sederhana, sebuah query merupakan suatu keywords (kata kunci) dan dokumen yang mengandung keywords merupakan dokumen yang dicari dalam IR.

 

3.HITS Algorithm?
HITS algorithm adalah kepanjangan dari Hyperlink-Induced Topic Search yaitu adalah algoritma link analysis yang dapat digunakan dalam pencarian dokumen yang relevan dan populer.HITS menggunakan root set sebagai data awal, root set tersebut akan diperluas menjadi base set dan dari base set akan digunakan dalam perhitungan nilai authority dan hub.

4.Prolog

Prolog adalah bahasa pemrograman logika atau di sebut juga sebagai bahasa non-procedural. Bahasa ini dibuat untuk menciptakan suatu bahasa pemrograman yang memungkinkan pernyataan logika alih-alih rangkaian perintah untuk dijalankan komputer.

Berbeda dengan bahasa pemrograman yang lain, yang menggunakan algoritma konvensionl sebagai teknik pencariannya seperti pada Delphi, Pascal, BASIC, COBOL, dan bahasa pemrograman yang sejenisnya, maka prolog menggunakan teknik pencarian yang di sebut heuristik (heutistic) dengan menggunakan pohon logika.

I.       Pendahuluan

            Video merupakan salah satu bagian dari hidup kita sekarang, hampir setiap kali kita melihat video di keseharian kita. Video merupakan serangkaian gambar yang bergerak sebegitu cepat sehingga kita melihatnya seolah-olah bergerak, biasanya digabungkan dengan suara sehingga menjadi satu video atau film utuh. Video merupakan suatu bagian dari multimedia, karena di dalamnya ada banyak (multi) media (media) yaitu gambar, audio bahkan bisa dimasukkan text dan lain – l–innya. Kelompok kami mengerjakan tugas multimedia ini membuat video yang bertemakan “ Tempat yang Nyaman untuk Bersantai “ yang menggunakan alat kamera Handphone Samsung Note 3 milik Ivan. Kami mengedit video kami menggunakan software “ Adobe Premiere Elements 8.0 “, Berformat MPEG dan berukuran 300Mb. Kami mengunjungi total 3 tempat terbaik dari sekian tempat yang ada di sekitar binus (Menurut Kami).

II.     Timeline, Story Board dan Penjelasan Skenario

 1.     Story Board

2.     Penjelasan Skenario

Dalam pembuatan project system multimedia yaitu membuat video yang bertema bebas. Kami menentukan tema dalam video kami adalah, “Tempat yang nyaman untuk bersantai dikala menunggu kelas yang kosong, atau dalam mebuat tugas.” Kami membuat video ini dengan latar beberapa tempat yang sudah kami survey kenyamanan dan kualitas yang di tawarkan oleh tempat tersebut.

Pertama, kami mengunjungi “indomaret point” yang berlokasi di sebelah alfamart jaan kebun jeruk raya. Dalam scene tersebu, Ivan Sunaryo sebagai perwakilan kelompok kami, yang bertugas melakukan opening dan menjelaskan tujuan dari video kami. Setelah itu kami berada di dalam indomaret point lantai 2, dan meng-interview dan meminta opini pengunjung(Nauval dan Yohan) yang menikmati fasilitas yang di sediakan oleh tempat tersebut.

Kedua, setelah mengunjungi indomaret point, Scene kedua kami menunjukan tampilan luar dari “Seven Eleven”, yang bertempat di Kh.Syahdan No.1. Kami menampilkan latar lantai 2 dan menjelaskan perbedaan dari indomaret point dan menginterview beberapa penikmat tempat tersebut(Vincent dan Chris).

Dan yang terakhir kami mengunjungi “Loving Hut” yang bertempatan di ”gang Keluarga”. Disana Ivan menjelaskan perbedaan Loving Hut dari tempat lainnya, dan di dalam kami menginterview penikmat(Vincent) dari sajian Loving Hut yang bertemakan vegetarian. Dan setelah menginterview, Ivan memberi penjelasan dari kelebihan memakan makananan vegetarian, dan Ivan melakukan penutupan.

Kesimpulan dari video kami, total lamanya video kami adalah 4 menit dan 3 detik, dengan komposisi 3 scene. Scene pertama, pembukaan dan menjelaskan indomaret point, scene kedua, menjelaskan seven-eleven, dan scene terakhir menjelaskan loving hut dan penutupan.

 

3. Timeline

4. Link Video

Berikut adalah link video kami : Video

III.  Penutup

Kesimpulan dari video kami adalah bahwa di sekitar binus banyak tempat nongkrong atau tempat yang nyaman untuk bersantai, namun ketiga ini lah yang paling tidak menurut kami merupakan tempat – tempat yang paling asik untuk ngobrol dan santai bareng, kami sering menemukan binusian juga kesini untuk bersantai.

welcome to me blog one’s again
pada kesempatan kali ini saya ingin share mengenai tugas saya
artificial Intelegence mengenai Learning by Example

1. Apa yang dimaksud supervised learning, unsupervised learning dan reinforcement learning?

– Supervised learning : merupakan suatu pembelajaran yang terawasi dimana jika output yang diharapkan telah diketahui sebelumnya. Biasanya pembelajaran ini dilakukan dengan menggunakan data yang telah ada.

Atau

teknik pembelajaran mesin dengan membuat suatu fungsi dari data latihan. Data latihan terdiri dari pasangan nilai input dan output yang diharapkan dari input yang bersangkutan. Tugas dari Supervised learning adalah untuk memprediksi nilai fungsi untuk nilai semua input yang ada.

Contoh :

– Sebagai contoh ada data luas rumah (x) dan harga (y). lalu dimasukkan dalam grafik x dan y-nya. Dimana setelah itu dibuat regresi antara x dan y-nya. Setelah membuat regresi dapat dipastikan kita dapat memprediksi dari hasil regresi harga rumah dengan luas tertentu.
– Contoh algoritma jaringan saraf tiruan yang mernggunakan metode supervised learning adalah hebbian (hebb rule), perceptron, adaline, boltzman, hapfield, dan backpropagation.
– Misalnya sebuah program diberikan benda berupa bangku dan meja, maka setelah beberapa contoh, program tersebut harus dapat memilah- milah objek ke dalam klasifikasi yang cocok. Kesulitan dari supervised learning adalah kita tidak dapat membuat klasifikasi yang benar. Dapat dimungkinkan program akan salah dalam mengklasifikasi sebuah objek setelah dilatih. Oleh karena itu, selain menggunakan training set kita juga memberikan test set. Dari situ kita akan mengukur persentase keberhasilannya. Semakin tinggi berarti semakin baik program tersebut. Persentase tersebut dapat ditingkatkan dengan diketahuinya temporal dependence dari sebuah data. Misalnya diketahui bahwa 70% mahasiswa dari jurusan Teknik Informatika adalah laki- laki dan 80% mahasiswa dari jurusan Sastra adalah wanita. Maka program tersebut akan dapat mengklasifikasi dengan lebih baik.

berikut cth gambarnya 😀

– Unsupervised learning : merupakan pembelajan yang tidak terawasi dimana tidak memerlukan target output. Pada metode ini tidak dapat ditentukan hasil seperti apa yang diharapkan selama proses pembelajaran, nilai bobot yang disusun dalam proses range tertentu tergantung pada nilai output yang diberikan. Tujuan metode uinsupervised learning ini agar kita dapat mengelompokkan unit-unit yang hampir sama dalam satu area tertentu. Pembelajaran ini biasanya sangat cocok untuk klasifikasi pola.

Atau

Teknik ini menggunakan prosedur yang berusaha untuk mencari partisi dari sebuah pola. Unsupervised learning mempelajari bagaimana sebuah sistem dapat belajar untuk merepresentasikan pola input dalam cara yang menggambarkan struktur statistikal dari keseluruhan pola input. Berbeda dari supervised learning, unsupervised learning tidak memiliki target output yang eksplisit atau tidak ada pengklasifikasian input.
Dalam machine learning, teknik unsupervised sangat penting. Hal ini dikarenakan cara bekerjanya mirip dengan cara bekerja otak manusia. Dalam melakukan pembelajaran, tidak ada informasi dari contoh yang tersedia. Oleh karena itu, unsupervised learning menjadi esensial.

Contoh :

– Contoh algoritma jaringan saraf tiruan yang menggunakan metode unsupervised ini adalah competitive, hebbian, kohonen, LVQ(Learning Vector Quantization), neocognitron.
– Competitive learning, di mana neuron-neuron saling bersaing untuk menjadi pemenang.
– Ilustrasi yang mudah misalkan hubungan antara murid dan dosen pada contoh yang sebelumnya. Ketika si murid menjumpai masalah, ia harus dapat menjawab masalah tersebut dengan sendirinya. Semakin banyak ia berusaha menjawab sendiri, ia akan semakin pandai dalam menemukan rule yang dapat digunakan untuk memecahkan permasalahan di kemudian hari.

berikut contoh gambarny 😀

– Reinforcement learning : Konsep dasar reinforcement learning diambil dari suatu teori dalam ilmu psikologi yang disebut dengan reinforcement theory. Reinforcement theory ini merupakan suatu pendekatan psikologi yang sangat penting bagi manusia. Teori ini menjelaskan bagaimana seseorang itu dapat menentukan, memilih dan mengambil keputusan dalam dinamika kehidupan. Kelebihan lain dari teori ini dapat digunakan pada berbagai macam situasi yang seringkali dihadapi manusia (Bertsekas, 1996 : 2).

Menurut Masayu Leylia (2003:2) reinforcement learning merupakan pembelajaran hasil interaksi dengan lingkungan, sehingga dapat diperoleh maximal cummulative reward saat goal tercapai. Hal senada diungkapkan oleh Ali Ridho Barakbah (2007:3-6) reinforcement learning adalah salah satu paradigma baru di dalam learning theory. Reinforcement learning dibangun dari proses mapping (pemetaan) dari situasi yang ada di environment (states) ke bentuk aksi (behavior) agar dapat memaksimalkan reward. Reinforcement learning secara umum terdiri dari 4 komponen dasar, yaitu: (a) policy : kebijaksanaan, (b) reward function, (c) value function, dan (d) model of environment.

Contoh :

– Contoh yang realistis, AI dalam permainan, seperti catur atau monopoli. Kalau agen itu pintar dan menang, di dapat hadiah, atau sekedar ucapan ‘Selamat Anda Menang’ dan kalau kalah tentu saja ucapan yang berlawanan.
– Contoh yang paling mudah yang bisa saya gambarkan disini adalah bagaimana sikap yang diambil oleh seorang siswa di dalam kelas. Asumsikan bahw a sang guru sudah menjelaskan seperangkap aturan yang harus ditaati oleh siswa di dalam kelas. Suatu ketika, seorang siswa berteriak di dalam kelas. Maka sang guru langsung memberikan hukuman kepada siswa tersebut. Dari hukuman itu, siswa tadi akan merubah sikapnya untuk tidak berteriak lagi. Juga demikian, kepada siswa yang tekun mengikuti pelajaran di dalam kelas, maka sang guru memberikan kepada mereka semacam hadiah atau penghargaan. Jika sistem ini berjalan dalam jangka waktu tertentu, maka keadaan siswa tadi pasti akan konvergen untuk mengambil sikap yang baik di dalam kelas.

berikut contoh gambarny 😀

 

2. Apa yang dimaksud dengan Learning Decision Tree ?

– Secara singkat bahwa Decision Tree merupakan salah satu metode klasifikasi pada Text Mining. Klasifikasi adalah proses menemukan kumpulan pola atau fungsi-fungsi yang mendeskripsikan dan memisahkan kelas data satu dengan lainnya, untuk dapat digunakan untuk memprediksi data yang belum memiliki kelas data tertentu (Jianwei Han, 2001).
– Decision Tree adalah sebuah struktur pohon, dimana setiap node pohon merepresentasikan atribut yang telah diuji, setiap cabang merupakan suatu pembagian hasil uji, dan node daun (leaf) merepresentasikan kelompok kelas tertentu. Level node teratas dari sebuah Decision Tree adalah node akar (root) yang biasanya berupa atribut yang paling memiliki pengaruh terbesar pada suatu kelas tertentu. Pada umumnya Decision Tree melakukan strategi pencarian secara top-down untuk solusinya. Pada proses mengklasifikasi data yang tidak diketahui, nilai atribut akan diuji dengan cara melacak jalur dari node akar (root) sampai node akhir (daun) dan kemudian akan diprediksi kelas yang dimiliki oleh suatu data baru tertentu.

Contoh :

Beberapa Terms Examples (S), adalah training examples yang ditunjukkan oleh tabel di bawah ini:

Target attribute adalah PlayTennis yang memiliki value yes atau no, selama 14 minggu pada setiap Sabtu pagi. Attribute adalah Outlook, Temperature, Hunidity, dan Wind.

Algoritma
PROCEDURE ID3(Examples, TargetAttribute, Attributes)5
Examples are the training examples. Target-attribute is the attribute whose value is to be
predicted by the tree. Attributes is a list of other attributes that may be tested by the
learned decision tree. Returns a decision tree that correctly classifies the given Examples.
• Create a Root node for the tree
• If all Examples are positive, Return the single-node tree Root, with label = +
• If all Examples are negative, Return the single-node tree Root, with label = –
• If Attributes is empty, Return the single-node tree Root, with label = most common
value of Target_attribute in Examples
• Otherwise Begin
• A <— the attribute from Attributes that best* classifies Examples
• The decision attribute for Root <— A
• For each possible value, vi, of A,
• Add a new tree branch below Root, corresponding to the test A = vi
• Let Examplesvi be the subset of Examples that have value vi for A
• If Examplesvi is empty
• Then below this new branch add a leaf node with label = most common
• value of Target_attribute in Examples
• Else below this new branch add the subtree
• Call ID3 (Examples, Target_attribute, Attributes – {A}))
• End
• Return Root
The best attribute is the one with highes information gain, as defined in Equation:

 

S adalah koleksi dari 14 contoh dengan 9 contoh positif dan 5 contoh negatif, ditulis dengan notasi [9+,5-]. Entropy dari S adalah:

 

Entropy([9+,5-]) = – (9/14)log2(9/14) – (5/14)log2(5/14)
= 0.94029
Catatan:

 

• Entropy(S)=0, jika semua contoh pada S berada dalam kelas yang sama.
• Entropy(S)=1, jika jumlah contoh positif dan jumlah contoh negatif dalam S adalah sama.
• 0<Entropy(S)<1, jika jumlah contoh positif dan negatif dalam S tidak sama.
Gain(S,A) adalah Information Gain dari sebuah attribute A pada koleksi contoh S.6

Values(Wind) = Weak, Strong
SWeak           = [6+,2-]
SStrong         = [3+,3-]
Gain(S,Wind) = Entropy(S) – (8/14)Entropy(SWeak) – (6/14)Entropy(SStrong)
= 0.94029 – (8/14)0.81128 – (6/14)1.0000
= 0.04813

Values(Humidity) = High, Normal
SHigh                  = [3+,4-]
SNormal              = [6+,1-]
Gain(S,Humidity) = Entropy(S) – (7/14)Entropy(SHigh) – (7/14)Entropy(SNormal)
= 0.94029 – (7/14)0.98523 – (7/14)0.59167
= 0.15184

Values(Temperature) = Hot, Mild, Cool
SHot                          = [2+,2-]
SMild                         = [4+,2-]
SCool                        = [3+,1-]
Gain(S,Temperature)  = Entropy(S) – (4/14)Entropy(SHot) – (6/14)Entropy(SMild)- (4/14)Entropy(SCool)
= 0.94029 – (4/14)1.00000 – (6/14)0.91830 – (4/14)0.81128
= 0.02922

Values(Outlook) = Sunny, Overcast, Rain
SSunny               = [2+,3-]
SOvercast           = [4+,0-]
SRain                  = [3+,2-]
Gain(S,Outlook)  = Entropy(S) – (5/14)Entropy(SSunny) – (4/14)Entropy(SOvercast)
-(5/14)Entropy(SRain)
= 0.94029 – (5/14)0.97075 – (4/14)1.000000 – (5/14)0.97075
= 0.24675

Jadi, information gain untuk 4 atribut yang ada adalah:
Gain(S,Wind)             = 0.04813
Gain(S,Humidity)      = 0.15184
Gain(S,Temperature) = 0.02922
Gain(S,Outlook)        = 0.24675
Dari perhitungan tersebut, tampak bahwa attribute Outlook akan menyediakan prediksi terbaik untuk target attribute PlayTennis.

 

 

Untuk branch node Outlook=Sunny,
SSunny = [D1, D2, D8, D9, D11]

 

Values(Temperature)          = Hot, Mild, Cool
SHot                                   = [0+,2-]
SMild                                  = [1+,1-]
SCool                                  = [1+,0-]
Gain(SSunny, Temperature) = Entropy(SSunny) – (2/5)Entropy(SHot) – (2/5)Entropy(SMild)
– (1/5)Entropy(SCold)
= 0.97075 – (2/5)0.00000 – (2/5)1.00000 – (1/5)0.00000
= 0.57075

Values(Humidity)           = High, Normal
SHigh                             = [0+,3-]
SNormal                         = [2+,0-]
Gain(SSunny, Humidity) = Entropy(SSunny) – (3/5)Entropy(SHigh) – (2/5)Entropy(SNormal)
= 0.97075 – (3/5)0.00000 – (2/5)1.00000
= 0.97075
Values(Wind)           = Weak, Strong
SWeak                     = [1+,2-]
SStrong                   = [1+,1-]
Gain(SSunny, Wind) = Entropy(SSunny) – (3/5)Entropy(SWeak) – (2/5)Entropy(SStrong)
= 0.97075 – (3/5)0.91830 – (2/5)1.00000
= 0.01997

Untuk branch node Outlook=Rain,
SRain = [D4, D5, D6, D10, D14]

Values(Temperature)        = Mild, Cool {Tidak ada lagi temperature=hot saat ini}
SMild                                = [2+,1-]
SCool                               = [1+,1-]
Gain(SRain, Temperature) = Entropy(SRain) – (3/5)Entropy(SMild) – (2/5)Entropy(SCold)
= 0.97075 – (3/5)0.91830 – (2/5)1.00000
= 0.01997
Values(Humidity)        = High, Normal
SHigh                          = [1+,1-]
SNormal                      = [2+,1-]
Gain(SRain, Humidity) = Entropy(SRain) – (2/5)Entropy(SHigh) – (3/5)Entropy(SNormal)
= 0.97075 – (2/5)1.00000 – (3/5)0.91830
= 0.01997
Values(Wind)        = Weak, Strong
SWeak                  = [3+,0-]
SStrong                = [0+,2-]
Gain(SRain, Wind) = Entropy(SRain) – (3/5)Entropy(SWeak) – (2/5)Entropy(SStrong)
= 0.97075 – (3/5)0.00000 – (2/5)0.00000
= 0.97075

Rule-Rule yang telah Dipelajari, dengan memperhatikan decision tree yang dihasilkan adalah :
• IF Outlook = Sunny AND Humidity = High THEN PlayTennis = No
• IF Outlook = Sunny AND Humidity = Normal THEN PlayTennis = Yes
• IF Outlook = Overcast THEN PlayTennis = Yes
• IF Outlook = Rain AND Wind = Strong THEN PlayTennis = No
• IF Outlook = Rain AND Wind = Weak THEN PlayTennis = Yes

 

Selamat datang di blog saya 😉
Pada kesempatan ini saya ingin share informasi tentang Matakuliah Intelegensi semu 😀 smoga bermanfaat 😉

– Adversial Search
apa itu adversial search? adversial search adalah algoritma pencarian untuk memeriksa masalah yang timbul ketika kita mencoba untuk merencanakan suatu langkah ke depan tetapi ada player atau pihak lain berencana melawan cara kita, bisa juga digunakan dalam permainan dimana player mencoba untuk mendapatkan nilai / score tertinggi, namun di tentang oleh pemain lain (bisa berupa AI/komputer yg menjalankan / user lain yang menjalankan)

biasanya cara ini digunakan dalam permainan reversi, catur, go, tic tac toe, dan masih banyak lainnya

contoh Algoritma yang biasa digunakan: MiniMax, Alpha–beta pruning.
Algoritma yang biasa di gunakan adalah , MiniMax dan Alpha-beta pruning.

-Constraint Satisfaction Problems

Constraint Satisfaction Problems adalah metode yang paling mendekati atau sesuai dengan keinginan kita. Algoritma pencarian jenis ini, akan mencari solusi dengan cara memberikan berbagai alternatif pilihan dan tidak harus berurutan.

Komponen dari Constraint Satisfaction Problem terbagi atas 3 yaitu :

1. Variabel merupakan penampung yang dapat diisi berbagai nilai.
2. Domain merupakan kumpulan nilai legal yang dapat diisi ke variable.
3. Constraint merupakan suatu aturan yang ditentukan untuk mengatur nilai boleh diisikan ke variable atau kombonasi variable.

Constraint dari Constraint Satisfaction Problem terbagi atas 2 kategori yaitu :

• Hard Constraint adalah batasan yang harus dipenuhi dan tidak boleh dilanggar dalam pembuatan penyelasaian masalah.
• Soft Constraint adalah batasan tambahan yang biasanya merupakan sebuah permintaan.

Dalam beberapa masalah yang lebih kompleks, metode Constraint Satisfaction Problem ini bisa dipadukan dengan algoritma lainnya seperti :

• Algoritma Genetika
• Backtracking
• Forward Checking
• Constraint Propagation
• Arc and Path Consistency
• Variable and Value Ordering
• Hill Climbing

Contohnya : Cryptarithmetic,  Map Coloring,  Backtracking  Search

-Apa itu Logika Ropositional?

Propositional logic merupakan salah satu bentuk (bahasa) representasi logika yang paling tua dan paling sederhana. Dengan cara ini beberapa fakta dapat digambarkan dan dimanipulasi dengan menggunakan aturan-aturan aljabar Boolean.
biasanya bentuk bahasa ini bisa direpresentatifkan menggunakan kalimat maupun simbol

Contoh :

p : Ivan mau bermain drum

q : Lagunya bagus

premis 1 : q -> p

premis 2 : ~q

Kesimpulan : ~p

” Jika Lagunya bagus maka Ivan mau bermain drum” namun di premis 2 ” Lagunya tidak bagus ” Kesimpulannya  Ivan tidak mau bermain drum.

Berikut ada juga beberapa contoh coding Algoritma A & Algoritma A* (A Star) dalam Bahasa C++

Algoritma A*

#include <iostream>
#include <iomanip>
#include <queue>
#include <string>
#include <math.h>
#include <ctime>
using namespace std;

const int n=60; // horizontal size of the map
const int m=60; // vertical size size of the map
static int map[n][m];
static int closed_nodes_map[n][m]; // map of closed (tried-out) nodes
static int open_nodes_map[n][m]; // map of open (not-yet-tried) nodes
static int dir_map[n][m]; // map of directions
const int dir=8; // number of possible directions to go at any position
// if dir==4
//static int dx[dir]={1, 0, -1, 0};
//static int dy[dir]={0, 1, 0, -1};
// if dir==8
static int dx[dir]={1, 1, 0, -1, -1, -1, 0, 1};
static int dy[dir]={0, 1, 1, 1, 0, -1, -1, -1};

class node
{
    // current position
    int xPos;
    int yPos;
    // total distance already travelled to reach the node
    int level;
    // priority=level+remaining distance estimate
    int priority;  // smaller: higher priority

    public:
        node(int xp, int yp, int d, int p) 
            {xPos=xp; yPos=yp; level=d; priority=p;}

        int getxPos() const {return xPos;}
        int getyPos() const {return yPos;}
        int getLevel() const {return level;}
        int getPriority() const {return priority;}

        void updatePriority(const int & xDest, const int & yDest)
        {
             priority=level+estimate(xDest, yDest)*10; //A*
        }

        // give better priority to going strait instead of diagonally
        void nextLevel(const int & i) // i: direction
        {
             level+=(dir==8?(i%2==0?10:14):10);
        }

        // Estimation function for the remaining distance to the goal.
        const int & estimate(const int & xDest, const int & yDest) const
        {
            static int xd, yd, d;
            xd=xDest-xPos;
            yd=yDest-yPos;         

            // Euclidian Distance
            d=static_cast<int>(sqrt(xd*xd+yd*yd));

            // Manhattan distance
            //d=abs(xd)+abs(yd);

            // Chebyshev distance
            //d=max(abs(xd), abs(yd));

            return(d);
        }
};

// Determine priority (in the priority queue)
bool operator<(const node & a, const node & b)
{
  return a.getPriority() > b.getPriority();
}

// A-star algorithm.
// The route returned is a string of direction digits.
string pathFind( const int & xStart, const int & yStart, 
                 const int & xFinish, const int & yFinish )
{
    static priority_queue<node> pq[2]; // list of open (not-yet-tried) nodes
    static int pqi; // pq index
    static node* n0;
    static node* m0;
    static int i, j, x, y, xdx, ydy;
    static char c;
    pqi=0;

    // reset the node maps
    for(y=0;y<m;y++)
    {
        for(x=0;x<n;x++)
        {
            closed_nodes_map[x][y]=0;
            open_nodes_map[x][y]=0;
        }
    }

    // create the start node and push into list of open nodes
    n0=new node(xStart, yStart, 0, 0);
    n0->updatePriority(xFinish, yFinish);
    pq[pqi].push(*n0);
    open_nodes_map[x][y]=n0->getPriority(); // mark it on the open nodes map

    // A* search
    while(!pq[pqi].empty())
    {
        // get the current node w/ the highest priority
        // from the list of open nodes
        n0=new node( pq[pqi].top().getxPos(), pq[pqi].top().getyPos(), 
                     pq[pqi].top().getLevel(), pq[pqi].top().getPriority());

        x=n0->getxPos(); y=n0->getyPos();

        pq[pqi].pop(); // remove the node from the open list
        open_nodes_map[x][y]=0;
        // mark it on the closed nodes map
        closed_nodes_map[x][y]=1;

        // quit searching when the goal state is reached
        //if((*n0).estimate(xFinish, yFinish) == 0)
        if(x==xFinish && y==yFinish) 
        {
            // generate the path from finish to start
            // by following the directions
            string path="";
            while(!(x==xStart && y==yStart))
            {
                j=dir_map[x][y];
                c='0'+(j+dir/2)%dir;
                path=c+path;
                x+=dx[j];
                y+=dy[j];
            }

            // garbage collection
            delete n0;
            // empty the leftover nodes
            while(!pq[pqi].empty()) pq[pqi].pop();           
            return path;
        }

        // generate moves (child nodes) in all possible directions
        for(i=0;i<dir;i++)
        {
            xdx=x+dx[i]; ydy=y+dy[i];

            if(!(xdx<0 || xdx>n-1 || ydy<0 || ydy>m-1 || map[xdx][ydy]==1 
                || closed_nodes_map[xdx][ydy]==1))
            {
                // generate a child node
                m0=new node( xdx, ydy, n0->getLevel(), 
                             n0->getPriority());
                m0->nextLevel(i);
                m0->updatePriority(xFinish, yFinish);

                // if it is not in the open list then add into that
                if(open_nodes_map[xdx][ydy]==0)
                {
                    open_nodes_map[xdx][ydy]=m0->getPriority();
                    pq[pqi].push(*m0);
                    // mark its parent node direction
                    dir_map[xdx][ydy]=(i+dir/2)%dir;
                }
                else if(open_nodes_map[xdx][ydy]>m0->getPriority())
                {
                    // update the priority info
                    open_nodes_map[xdx][ydy]=m0->getPriority();
                    // update the parent direction info
                    dir_map[xdx][ydy]=(i+dir/2)%dir;

                    // replace the node
                    // by emptying one pq to the other one
                    // except the node to be replaced will be ignored
                    // and the new node will be pushed in instead
                    while(!(pq[pqi].top().getxPos()==xdx && 
                           pq[pqi].top().getyPos()==ydy))
                    {                
                        pq[1-pqi].push(pq[pqi].top());
                        pq[pqi].pop();       
                    }
                    pq[pqi].pop(); // remove the wanted node

                    // empty the larger size pq to the smaller one
                    if(pq[pqi].size()>pq[1-pqi].size()) pqi=1-pqi;
                    while(!pq[pqi].empty())
                    {                
                        pq[1-pqi].push(pq[pqi].top());
                        pq[pqi].pop();       
                    }
                    pqi=1-pqi;
                    pq[pqi].push(*m0); // add the better node instead
                }
                else delete m0; // garbage collection
            }
        }
        delete n0; // garbage collection
    }
    return ""; // no route found
}

int main()
{
    srand(time(NULL));

    // create empty map
    for(int y=0;y<m;y++)
    {
        for(int x=0;x<n;x++) map[x][y]=0;
    }

    // fillout the map matrix with a '+' pattern
    for(int x=n/8;x<n*7/8;x++)
    {
        map[x][m/2]=1;
    }
    for(int y=m/8;y<m*7/8;y++)
    {
        map[n/2][y]=1;
    }

    // randomly select start and finish locations
    int xA, yA, xB, yB;
    switch(rand()%8)
    {
        case 0: xA=0;yA=0;xB=n-1;yB=m-1; break;
        case 1: xA=0;yA=m-1;xB=n-1;yB=0; break;
        case 2: xA=n/2-1;yA=m/2-1;xB=n/2+1;yB=m/2+1; break;
        case 3: xA=n/2-1;yA=m/2+1;xB=n/2+1;yB=m/2-1; break;
        case 4: xA=n/2-1;yA=0;xB=n/2+1;yB=m-1; break;
        case 5: xA=n/2+1;yA=m-1;xB=n/2-1;yB=0; break;
        case 6: xA=0;yA=m/2-1;xB=n-1;yB=m/2+1; break;
        case 7: xA=n-1;yA=m/2+1;xB=0;yB=m/2-1; break;
    }

    cout<<"Map Size (X,Y): "<<n<<","<<m<<endl;
    cout<<"Start: "<<xA<<","<<yA<<endl;
    cout<<"Finish: "<<xB<<","<<yB<<endl;
    // get the route
    clock_t start = clock();
    string route=pathFind(xA, yA, xB, yB);
    if(route=="") cout<<"An empty route generated!"<<endl;
    clock_t end = clock();
    double time_elapsed = double(end - start);
    cout<<"Time to calculate the route (ms): "<<time_elapsed<<endl;
    cout<<"Route:"<<endl;
    cout<<route<<endl<<endl;

    // follow the route on the map and display it 
    if(route.length()>0)
    {
        int j; char c;
        int x=xA;
        int y=yA;
        map[x][y]=2;
        for(int i=0;i<route.length();i++)
        {
            c =route.at(i);
            j=atoi(&c); 
            x=x+dx[j];
            y=y+dy[j];
            map[x][y]=3;
        }
        map[x][y]=4;

        // display the map with the route
        for(int y=0;y<m;y++)
        {
            for(int x=0;x<n;x++)
                if(map[x][y]==0)
                    cout<<".";
                else if(map[x][y]==1)
                    cout<<"O"; //obstacle
                else if(map[x][y]==2)
                    cout<<"S"; //start
                else if(map[x][y]==3)
                    cout<<"R"; //route
                else if(map[x][y]==4)
                    cout<<"F"; //finish
            cout<<endl;
        }
    }
    getchar(); // wait for a (Enter) keypress  
    return(0);
}

Welcome to Binusian blog.
This is the first post of any blog.binusian.org member blog. Edit or delete it, then start blogging!
Happy Blogging 🙂