Rust アンテナ選択 貪欲

rust_antenna_greedy.rs

use rand::{Rng, thread_rng};
use rand::distributions::{Uniform};
use std::collections::{HashMap, HashSet};

#[allow(dead_code)]
struct Env {
    rg: f32,          // ランダム位置範囲 (-rg, rg)
    n: usize,         // アンテナ数
    r: f32,           // アンテナの半径
    a: Vec<[f32; 2]>, // アンテナの位置
    m: usize,         // センサー個数
    x: Vec<[f32; 2]>, // センサーの位置
    c: HashMap<usize, HashSet<usize>>, // cover map
}

#[allow(dead_code)]
impl Env {
    pub fn new(rg: f32, n: usize, r: f32, m: usize) -> Self {
        let mut rng = thread_rng();
        let side = Uniform::new(-rg, rg);
        let mut a = vec![[0.0, 0.0]; 10];
        for i in 0..n {
            a[i][0] = rng.sample(side) as f32;
            a[i][1] = rng.sample(side) as f32;
        }

        let mut x = vec![[0.0, 0.0]; m];
        for i in 0..m {
            x[i][0] = rng.sample(side) as f32;
            x[i][1] = rng.sample(side) as f32;
        }
        let mut cover = HashMap::new();
        for i in 0..n {
            let mut cover_i = HashSet::new();
            for j in 0..m {
                let xj = &x[j];
                let dist = ((a[i][0] - xj[0]).powf(2.0) + (a[i][1] - xj[1]).powf(2.0)).sqrt();
                if dist < r as f32 {
                    cover_i.insert(j);
                }
            }
            cover.insert(i, cover_i);
        }

        Self { rg: rg, n: n, r: r, a: a, m: m, x: x, c: cover }
    }

    pub fn f(&self, s: &HashSet<usize>) -> usize {
        let mut covered = 0;
        for _s in s {
            covered += self.c[_s].len();
        }
        return covered
    }

    pub fn print(&self) {
        println!("# Antenna [n={},r={}/rg={}]", self.n, self.r, self.rg);
        for i in 0..self.n {
            println!("{},{}", self.a[i][0], self.a[i][1]);
        }
        println!("# Sensor [m={}/rg={}]", self.m, self.rg);
        for i in 0..self.m {
            println!("{},{}", self.x[i][0], self.x[i][1]);
        }
    }
}

fn main() {
    let rg = 5.0;
    let r = 3.0;
    let n = 6;
    let m = 30;
    let env = Env::new(rg, n, r, m);
    // env.print();

    // 関数の例
    {
        let s1: HashSet<usize> = vec![1, 2].into_iter().collect();
        println!("{:?} -> {:?}", s1, env.f(&s1));
        let s2: HashSet<usize> = vec![1, 2, 3, 4].into_iter().collect();
        println!("{:?} -> {:?}", s2, env.f(&s2));
    }

    // greedy cover
    let k = 3;
    let mut s = HashSet::new();
    while s.len() < k {
        let mut ii = 0;
        let mut v = 0;
        for i in 0..n {
            if !s.contains(&i) {
                let mut si: HashSet<usize> = s.clone();
                si.insert(i);
                let vi = env.f(&si);
                if vi >= v {
                    ii = i;
                    v = vi;
                }
            }
        }
        s.insert(ii);
    }

    println!("{:?}, {}", s, env.f(&s));
}