人工知能に使われるようなアルゴリズムをいろんな言語で実装してみた

aster_puzzle.rs

// A*探索で5パズル（スライドパズルの簡易版）
use std::cmp::Ordering;
use std::collections::BinaryHeap;
use std::collections::HashMap;
use std::vec::Vec;
use std::usize;

// Utility
// print board
// 6 is empty
fn print_board(board: &mut [usize; 6]) {
    println!("{0} | {1} | {2}", board[0]+1, board[1]+1, board[2]+1);
    println!("{0} | {1} | {2}\n", board[3]+1, board[4]+1, board[5]+1);
}

// Heuristic Method
fn h(board: &mut [usize; 6]) -> usize {
    let mut ret = 0;
    for i in 0..6 {
        if board[i] != i { ret += 1; }
    }
    ret
}

// Priority Queue
// Including puzzle state as hash value
const FACTOR: [usize; 6] = [1, 1, 2, 6, 24, 120];
fn gen_hash(board: &mut [usize; 6]) -> usize {
    let value = board;
    for i in 0..6 {
        for j in (i+1)..6 {
            if value[j] > value[i] { value[j] -= 1; }
        }
    }
    let mut hash = 0;
    for i in 0..6 {
        hash += value[i] * FACTOR[5-i];
    }
    for i in (0..6).rev() {
        for j in (i+1)..6 {
            if value[i] <= value[j] { value[j] += 1; }
        }
    }
    hash
}

fn dehash(key: usize) -> [usize; 6] {
    let mut board = [0; 6];
    let mut mkey = key;
    for i in 0..6 {
        board[i] = mkey / FACTOR[5-i];
        mkey %= FACTOR[5-i];
    }
    for i in (0..6).rev() {
        for j in (i+1)..6 {
            if board[i] <= board[j] { board[j] += 1; }
        }
    }
    board
}

#[derive(Copy, Clone, Eq, PartialEq)]
struct State {
    cost: usize,
    position: usize,
}
impl Ord for State {
    fn cmp(&self, other: &State) -> Ordering {
        let other_cost = other.cost + h(&mut dehash(other.position));
        let self_cost = self.cost + h(&mut dehash(self.position));
        other_cost.cmp(&self_cost)
            .then_with(|| self.position.cmp(&other.position))
    }
}
impl PartialOrd for State {
    fn partial_cmp(&self, other: &State) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

// A* Search

fn aster_search(start: usize, goal: usize) -> Option<usize> {
    let mut dist = HashMap::new();
    let mut heap = BinaryHeap::new();
    let movable: [Vec<usize>; 6] = [vec![1, 3], vec![0, 2, 4], vec![1, 5], vec![0, 4], vec![1, 3, 5], vec![2, 4]];

    dist.insert(start, 0 as usize);
    heap.push(State { cost: 0, position: start });

    while let Some(State { cost, position }) = heap.pop() {
        if position == goal { return Some(cost) }

        if let Some(&dcost) = dist.get(&position) {
            if cost > dcost { continue; }
        }

        let mut current_board = &mut dehash(position);
        let mut empty_pos = 9;
        for i in 0..6 {
            if current_board[i] == 5 {
                empty_pos = i;
                break;
            }
        }

        println!("cost: {}---", cost);
        print_board(&mut *current_board);

        for &adj in &movable[empty_pos] {
            current_board.swap(adj, empty_pos);

            let next = State { cost: cost + 1, position: gen_hash(&mut current_board) };

            if let Some(&dcost) = dist.get(&next.position) {
                if next.cost < dcost {
                    heap.push(next);
                    dist.insert(next.position, next.cost);
                }
            } else {
                heap.push(next);
                dist.insert(next.position, next.cost);
            }

            current_board.swap(adj, empty_pos);
        }
    }

    None
}

fn main() {
    let mut start: [usize; 6] = [3, 2, 4, 1, 0, 5];
    let mut goal: [usize; 6]  = [0, 1, 2, 3, 4, 5];

    if let Some(ret) = aster_search(gen_hash(&mut start), gen_hash(&mut goal)) {
        println!("result is {}", ret);
    } else {
        println!("not found valid solution");
    }
}

dijkstra_maze.go

// Dijkstraで迷路探索
package main

import (
	"container/heap"
	"fmt"
)

type Node struct {
	dist  int
	name  int
	index int
}

type Edge struct {
	cost int
	to   int
}

// Priority Queue
type PriorityQueue []*Node

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].dist < pq[i].dist
}
func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}
func (pq *PriorityQueue) Push(x interface{}) {
	n := len(*pq)
	node := x.(*Node)
	node.index = n
	*pq = append(*pq, node)
}
func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	item.index = -1
	*pq = old[0 : n-1]
	return item
}
func (pq *PriorityQueue) update(node *Node, dist int, name int) {
	node.dist = dist
	node.name = name
	heap.Fix(pq, node.index)
}

// Dijkstra
var names = [10]string{"A", "B", "C", "D", "E", "F", "G", "H", "I", "J"}
var dist [10]int
var G [10][]Edge

func makeMap() {

	G[0] = []Edge{Edge{cost: 1, to: 1}, Edge{cost: 2, to: 3}}
	G[1] = []Edge{Edge{cost: 1, to: 0}, Edge{cost: 2, to: 2}}
	G[2] = []Edge{Edge{cost: 2, to: 1}, Edge{cost: 1, to: 6}}
	G[3] = []Edge{Edge{cost: 2, to: 0}, Edge{cost: 1, to: 4}}
	G[4] = []Edge{Edge{cost: 1, to: 3}, Edge{cost: 2, to: 5}}
	G[5] = []Edge{Edge{cost: 2, to: 4}, Edge{cost: 1, to: 6}}
	G[6] = []Edge{Edge{cost: 1, to: 5}, Edge{cost: 1, to: 2}, Edge{cost: 1, to: 7}}
	G[7] = []Edge{Edge{cost: 1, to: 6}, Edge{cost: 1, to: 8}, Edge{cost: 2, to: 9}}
	G[8] = []Edge{Edge{cost: 1, to: 7}}
	G[9] = []Edge{Edge{cost: 2, to: 7}}
}

func dijkstra(s int) {
	for i := 0; i < 10; i++ {
		dist[i] = 10000000000000
	}
	dist[s] = 0

	pq := make(PriorityQueue, 0)
	heap.Init(&pq)
	heap.Push(&pq, &Node{dist: 0, name: s})

	for pq.Len() > 0 {
		node := heap.Pop(&pq).(*Node)
		v := node.name
		d := node.dist
		if dist[v] < d {
			continue
		}
		fmt.Printf("%s: %d\nnext is ", names[v], d)
		for i := 0; i < len(G[v]); i++ {
			e := G[v][i]
			fmt.Printf("%s ", names[e.to])
			if dist[e.to] > dist[v]+e.cost {
				dist[e.to] = dist[v] + e.cost
				heap.Push(&pq, &Node{dist: dist[e.to], name: e.to})
			}
		}
		fmt.Printf("\n")
	}
}

func main() {

	makeMap()
	dijkstra(0)
	for i := 0; i < len(names); i++ {
		fmt.Printf("%s: %d\n", names[i], dist[i])
	}
	fmt.Printf("\nresult is %d\n", dist[9])
}

GreedyMaze.swift

// 貪欲最適探索で迷路探索
import Foundation

class Maze {
    
    struct Point: Comparable, Equatable {
        let x: Int
        let y: Int
        let label: String
        let connectedLabel: [String]
        
        var manhattan: Int {
            
            get {
                
                return abs(self.x - 3) + abs(self.y - 3)
            }
        }
        
        init(x: Int, y: Int, label: String, connectedLabel: [String]) {
            
            self.x = x
            self.y = y
            self.label = label
            self.connectedLabel = connectedLabel
        }
        
        func connectedPoints(_ points: [Point]) -> [Point] {
            
            return connectedLabel.map { label in points.filter({ $0.label == label }).first! }
        }
        
        static func < (lhs: Point, rhs: Point) -> Bool {
            
            return lhs.manhattan < rhs.manhattan
        }
        
        static func == (lhs: Point, rhs: Point) -> Bool {
            
            return lhs.manhattan == rhs.manhattan
        }
    }
    
    var mazeMap: [Point]!
    var closedList: [Point]!
    var openList: [Point]!
    
    func makeMap() {
        
        mazeMap = []
        mazeMap.append(Point(x: 1, y: 0, label: "A", connectedLabel: ["B", "D"]))
        mazeMap.append(Point(x: 0, y: 0, label: "B", connectedLabel: ["A", "C"]))
        mazeMap.append(Point(x: 0, y: 2, label: "C", connectedLabel: ["B", "G"]))
        mazeMap.append(Point(x: 3, y: 0, label: "D", connectedLabel: ["A", "E"]))
        mazeMap.append(Point(x: 3, y: 1, label: "E", connectedLabel: ["D", "F"]))
        mazeMap.append(Point(x: 1, y: 1, label: "F", connectedLabel: ["E", "G"]))
        mazeMap.append(Point(x: 1, y: 2, label: "G", connectedLabel: ["C", "H"]))
        mazeMap.append(Point(x: 1, y: 3, label: "H", connectedLabel: ["I", "J"]))
        mazeMap.append(Point(x: 0, y: 3, label: "I", connectedLabel: ["H"]))
        mazeMap.append(Point(x: 3, y: 3, label: "J", connectedLabel: ["H"]))
    }
    
    func search(_ cur: Point, cost: Int) -> Int {
        
        print("\(cur.label): \(cur.manhattan)")
        print("searching...")
        let nextList = cur.connectedPoints(mazeMap).filter({ point in
            
            !self.closedList.contains(where: { $0.label == point.label })
        })
        openList = (nextList + openList).unique
        print("openList \(openList ?? [])")
        let next = openList.min()!
        closedList.append(next)
        openList = openList.filter { $0.label != next.label }
        
        if next.label == "J" {
            
            return cost + abs(cur.x - next.x) + abs(cur.y - next.y)
        }
        return search(next, cost: cost + abs(cur.x - next.x) + abs(cur.y - next.y))
    }
}

extension Array where Element == Maze.Point {
    
    var unique: [Element] {
        
        var r = [Element]()
        for i in self {
            
            r += !r.contains(where: { $0.label == i.label }) ? [i] : []
        }
        return r
    }
}

func main() {
    
    let maze = Maze()
    maze.makeMap()
    maze.closedList = [maze.mazeMap[0]]
    maze.openList = []
    let result = maze.search(maze.mazeMap[0], cost: 0)
    print("result: \(result)")
}

main()

monte_carlo.py

# モンテカルロ法での円周率
#! /usr/bin/env python
# -*- coding: utf-8 -*-

import numpy as np
import numpy.random as random

def monte_carlo(n):
    # random number
    rx = random.rand(n) * 2.0 - 1.0
    ry = random.rand(n) * 2.0 - 1.0

    cnt = 0
    for (x, y) in zip(rx, ry):
        if x ** 2.0 + y ** 2.0 <= 1.0:
            cnt += 1

    return cnt * 4.0 / n

for n in [100, 1000, 10000, 100000, 1000000, 10000000]:
    print(n,monte_carlo(n),sep=': ')