Created
November 12, 2017 04:05
-
-
Save touyou/062592225d8ba66617de84f2ee1cb882 to your computer and use it in GitHub Desktop.
人工知能に使われるようなアルゴリズムをいろんな言語で実装してみた
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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"); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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]) | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 貪欲最適探索で迷路探索 | |
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() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# モンテカルロ法での円周率 | |
#! /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=': ') |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment