dijkstra算法 PHP 实现

20171119 利用周末优化了一下代码。这次完全默写了出来。感觉好多了

这个是根据算法图解自己写的,理解的不是很好,注释都在代码里面,过几天再默写一下,好好理解一下

<?php

// 构造图
$graphs = [];
$graphs['start'] = [];
$graphs['start']['a'] = 5;
$graphs['start']['b'] = 2;

$graphs['a'] = [];
$graphs['a']['c'] = 4;
$graphs['a']['d'] = 2;

$graphs['b'] = [];
$graphs['b']['a'] = 8;
$graphs['b']['d'] = 7;

$graphs['c'] = [];
$graphs['c']['d'] = 6;
$graphs['c']['fin'] = 3;

$graphs['d'] = [];
$graphs['d']['fin'] = 1;

$graphs['fin'] = [];

// 处理过的节点
$processed = [];
// 所有节点的消费
$costs = [];
// 所有节点的父节点
$parents = [];

function getNodeCost($graphs, $nodeName = 'start', $isStartNode = false)
{
    if (empty($graphs)) {
        return [];
    }
    $costs = [];
    foreach ($graphs[$nodeName] as $name => $length) {
        if ($isStartNode) {
            $costs[$name] = $length;
        } else {
            $costs[$name] = INF;
        }
        $costs += getNodeCost($graphs, $name);
    }

    return $costs;
}

$costs = getNodeCost($graphs, 'start', true);

function getNodeParents($graphs, $nodeName = 'start', $isStartNode = false)
{
    if (empty($graphs)) {
        return [];
    }
    $parents = [];
    foreach ($graphs[$nodeName] as $name => $length) {
        if ($isStartNode) {
            $parents[$name] = $nodeName;
        } else {
            $parents[$name] = null;
        }
        $parents += getNodeParents($graphs, $name);
    }

    return $parents;
}

$parents = getNodeParents($graphs, 'start', true);

function findLowestCostNode($costs, $processed)
{
    $lowestNodeLength = INF;
    $lowestNOdeName = '';
    foreach ($costs as $name => $length) {
        if ($length < $lowestNodeLength && !in_array($name, $processed)) {
            $lowestNodeLength = $length;
            $lowestNOdeName = $name;
        }
    }

    return $lowestNOdeName;
}

$nodeName = findLowestCostNode($costs, $processed);
while ($nodeName) {
    $currentNodeCost = $costs[$nodeName];
    foreach ($graphs[$nodeName] as $name => $length) {
        if ($currentNodeCost + $length < $costs[$name]) {
            $costs[$name] = $currentNodeCost + $length;
            $parents[$name] = $nodeName;
        }
    }
    $processed[] = $nodeName;
    $nodeName = findLowestCostNode($costs, $processed);
}

var_dump($costs);
var_dump($parents);

广度优先搜索 PHP 实现

直接上代码了,注释都在代码里面了。

<?php
/**
 * 广度搜索
 *
 * 你的朋友关系,以及朋友的朋友的关系,查看你的朋友或者朋友的朋友是不是包含 m 结尾的名字
 */

// 需要检索的数组
$graph = [];
$graph['you'] = ['alice', 'bob', 'claire'];
$graph['bob'] = ['anuj', 'peggy'];
$graph['alice'] = ['peggy'];
$graph['claire'] = ['thom', 'jonny'];
$graph['anuj'] = [];
$graph['peggy'] = [];
$graph['thom'] = [];
$graph['jonny'] = [];

// 搜索过的数组
$searchedItem = [];
// 待检索的数组
$waitSearchArray = [];
// 将第一层的关系加入到等待搜索的数组
$waitSearchArray = array_merge($waitSearchArray, $graph['you']);

// 将结果元素赋值为 false
$resultName = false;

//需要查找的字符
$findChar = 'z';

// 如果等待搜索的数组不为空就循环查找
while ($waitSearchArray) {
    // 从队列头部弹出一个元素
    $name = array_shift($waitSearchArray);
    // 如果待检查的元素在已经搜索过的数组中,就跳过,这个是用来防止循环检查的
    if (in_array($name, $searchedItem)) {
        continue;
    }
    // 获取最后一个字符
    $lastChar = substr($name, strlen($name) - 1, 1);
    // 如果最后一个字符是 m,就说明找到了,把结果赋值,然后跳出循环
    if ($lastChar == $findChar) {
        $resultName = $name;
        break;
    }

    // 到这里了说明没有找到,那么把这个人的名字,放入到已经搜索过的数组中
    $searchedItem[] = $name;
    // 然后再把这个名字的朋友关系加入到待搜索的数组中
    $waitSearchArray = array_merge($waitSearchArray, $graph[$name]);
}

var_dump($resultName);

29周岁生日快乐

一不小心29周岁了,在努力一下就而立了,所以这次就不努力了,慢慢来吧。

跟郝太太在一起已经一年半了,这一年半有争吵,有开心,有很多事情。当然最重要的是,房子买了,证也领了,啊哈哈哈。

最近一个月的学习效果也超级好,为半年后的折腾做准备吧。

图片alt

图片alt

图片alt

图片alt

蛋糕是郝太太给定的,好吃,喜欢

图片alt

菜是我做的,丑但是好吃

图片alt

键盘是我自己洗的,真他娘的累。

从来没想到郝太太会提前给我庆祝生日,原本是很开心的一天,还是被我偷偷抽烟惹到郝太太了,对于自己的承诺没有做到的确是我的错,所以还是诚恳的承认了错误,然后努力戒掉烟吧。

虽然现在比较苦,但是郝太太,别着急,给我点时间,会让生活更好的,有你的地方,就叫做家。

我想逃离舒适区了

昨天跟大学同学聊了两句,就说到了跳槽,正好我也有这方面的打算,当然不是现在,而是过一阵的计划。

但是,为了跳槽,自己也从现在就开始准备了。

从学校出来已经 4 年了,都是在一些不知名的小公司工作,然后在这种体量的公司做到了大家都比较认可的程度,现在反过来想想技术上面领先他们知识很小的一方面,更多的是对当前公司的架构啊,包括代码有了很深的了解。领先其他人的并不是技术,其实就是我比他们更熟悉而已。

迟到了3年的本科证准备在下个月申请毕业拿下,然后在明年看看能不能找到个大体量的公司进去拼搏一下。在最近的查看各种需求的时候发现自己欠缺了很多东西。其实欠缺的并不是当下流行的东西,那些东西我个人觉得,给一些时间就可以上手了。欠缺的则是很多基础的东西。所以也买了一些书,准备利用这几个月的时间学习一下以前自己落下的东西。

希望明年有个好的结果吧。逃离舒适区,然后进入困难模式,再把困难模式变成舒适区,继续挑战更难的模式,人一生就 3 万多天,在不折腾一下,对不起到此一游四个字。加油。

算法时空 第一周 基础部分

算法与计算

  • 计算:处理人类所不能处理的一些工作(难题),个人理解就是一些复杂性的难题,人类处理起来十分繁杂,计算机相比较容易,而且稳定性准确性更好。
  • 算法:输入->计算步骤->输出

排序问题:

  • 输入:n 个键值 (a1, a2,…,an)
  • 输出:升序输出
  • 例子:y, x, z -> x, y, z 。 按照字母顺序输出
  • 约束:序关系

优秀的算法:

  • 正确->思路清晰
  • 高效->算法分析
  • 易于实现->现成的算法

停机问题:是指算法能正确的停止下来 3n+1问题:有一个整数,如果是偶数就除以二,如果是奇数就是乘以3再加一,结果依次计算下去,看最后能不能变成1

算法的用处:

  • 生物信息学
  • 网络:图论, 字符串查找
  • 信息安全: RSA
  • 优化:调度

算法问题

  • 图论:最短路径
  • LCS: DP(动态规划)
  • 拓扑排序
  • 凸包

数据结构

速度差异